Ninja and Numbers

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
8 upvotes
Asked in companies
GoogleDeloitteCapegemini Consulting India Private Limited

Problem statement

Ninja has a number ‘A’ containing ‘B’ digits. ‘A’ can be represented by a string ‘S’ where ‘S[i]’ denotes the ‘ith’ digit of ‘A’. You are also given an integer ‘K’.

Ninja thinks that a number is stable if the following condition is satisfied:

For every ‘ith’ digit where (0 <= ‘i’ <= ‘B-1’) ‘S[i] = S[i%K]’. Here, ‘X%Y’ represents the modulo operations. The remainder when ‘X’ is divided by ‘Y’.

Your task is to find the smallest number which is stable and whose value is greater than or equal to ‘A’. Zero-based indexing is used everywhere.

Example : 
‘B’ = 4, ‘S’ = “4321”, ‘K’ = 3.
The given number is not stable as ‘S[3]’ is not the same as ‘S[0]’ but 3%3 = 0 same as 0%3. ‘S[3] = 1’ and ‘S[0] = 4’.  But the number “4324” is stable. As, for all ‘i’, ‘S[i]’ = ‘S[i%K]’ and “4324” is also greater than the given number. It can be proved that this is the best possible answer.
Hence, the answer is “4324”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains two single space-separated integers, ‘B’ and ‘K'.
The second line contains a string with ‘B’ characters representing the string ‘S’.
Output Format : 
For each test case, return the minimum stable number whose value is the same or exceeds the value of ‘A’.

Output for each test case will be printed on a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10
1 ≤ B ≤ 10^5
1 ≤ K ≤ 10^9
It’s guaranteed that sum of ‘B’ over all cases does not exceed 10^5. 
The given number will not contain leading zeros.

Time limit: 1 sec
Sample Input 1 :
2
4 2
6825
3 3
420
Sample Output 1 :
6868
420
Explanation For Sample Input 1 :
For test case 1: 
6868 is the minimum possible, stable number. We can see that it is stable because ‘S[0] = S[2]’ because 0%2 = 2%2, and ‘S[1] = S[3]’ because 1%2 = 3%2. All the conditions are satisfied.
Hence, 6868 is the answer.

For test case 2:
The given number itself is stable, and hence it is the best possible answer.
Sample Input 2 :
2
5 1
40369
4 2
8516
Sample Output 2 :
44444
8585
Hint

Which digits in the resulting number must be the same?

Approaches (1)
String Manipulation

Approach: 

  • The first ‘K’ digits of the given number are the most important ones from 0 to ‘K-1’. The other digits are just formed using them because if ‘i >= K’, then ‘S[i] = S[i%K]’ and ‘i%K < K’. Based on the definition of stable numbers.
  • Let us check if the stable number form using given ‘K’ digits is greater or equal to the given number.
    • For that create new number where for all (0 <= ‘i’ <= ‘B-1’) ‘CURR[i] = S[i%K]’. If ‘CURR’ is not smaller than ‘S’, the ‘CURR’ will be the answer.
  • Otherwise, just add 1 to the first ‘K’ digit:
    • To do that, find the last digit among the ‘K’ digits that is not ‘9’ and add 1 to it.
    • After adding 1, set all the digits on the right side to ‘0’.
  • Finally, form the complete answer by copying the other digits from the first ‘K’ digits. Just do ‘S[i] = S[i%K]’ for all index.

 

Algorithm: 

  • Declare a variable ‘n’ and set it to the size of the given string.
  • Create a string ‘currStable’ of length ‘n’ where ‘currStable[i] = s[i%k]’.
  • Now, if ‘currStable’ is greater or equal to ‘s’, then return ‘currStable’.
  • Declare a variable ‘ind’ = ‘k-1’.
    • While ‘s[ind]’ == ‘9’:- ‘ind- -’
    • Finally, we found an index where ‘s[ind]’ != ‘9’, incrementing this digit.
    • ‘s[ind]’++
  • Form the rest of the answer by looping through ‘i’ from ‘k’ to ‘n-1’ and setting ‘s[i] = s[i%k]’.
  • Return the final answer ‘s’.
Time Complexity

O(N), where ‘N’ is the number of digits in the given number.

We are visiting every digit at most twice. Hence the time complexity will be linear to that.

Hence, the time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of digits in the given number.

We are creating a new string and comparing it with the given string, which will take memory the same as the given string, which is linear.

Hence, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja and Numbers
Full screen
Console