Update appNew update is available. Click here to update.

Ninja and Numbers

profile
Contributed by
Smit Mistry
Medium
yellow-spark
0/80
25 mins
75 %
5 upvotes
CapgeminiGoogleDelloitte

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 )
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
Full screen
Reset Code
Full screen
Autocomplete
copy-code
Console