Solution 4 for Scaler Topics Fortnightly Contest - 15

This article is part of the Scaler Topics Fortnightly Contest - 15

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• We know xy can be written as (x*10 + y).
• Also if we want to append a digit z al the end of xy, we can write as xyz = (xy * 10 + z)
• Some properties of Modulo operation: (A + B) % M = (A % M + B % M) % M (A . B) % M = (A % M . B % M) % M
• Let the states of DP be dp[idx][cntN][aRem][bRem] where, idx denotes the current index we are at in the string A, cntN denotes the number of digits taken by Naaya in the prefix of string A till idx, aRem denotes the remainder left with Naaya, aRem denotes the remainder left with Haytham.
• At a particular index, we can either give that index to Naaya or Haytham, we both of them gives the minimum value of |x - y|, we prefer taking Naaya as we get the lexicographically largest string.

Time Complexity: O(|A| * |A| * B * C) Space Complexity: O(|A| * |A| * B * C)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation