Given two constructive integers X and Y (1 ≤ Y ≤ 105), discover the utmost constructive a number of (say M) of X such that M is lower than 10Y and all of the digits within the decimal illustration of M are equal.
Be aware: If no constructive a number of exists that satisfies the situations, return -1.
Examples:
Enter: X = 1, Y = 6
Output: 999999
Rationalization: 999999 is the biggest integer which is a a number of of 1, has all the identical digits and fewer than 106.Enter: X = 12, Y = 7
Output: 888888
Rationalization: 888888 is the biggest a number of of 12 which have all digits similar and is lower than 107.Enter: X = 25, Y = 10
Output: -1
Rationalization: No constructive integers M fulfill the situations.
Strategy: To resolve the issue comply with the beneath concept:
The principle concept is to contemplate all of the numbers lower than 10Y which have the identical digits in decimal illustration and examine if the quantity is a a number of of X, from all such multiples, the utmost one because the end result.
Observe the steps to unravel the issue:
- Contemplate a perform f(n, d) which denotes the rest of the quantity with size n and all digits d when divided by X.
- Calculate f(n, d) for each {n, d}.
- Discover that f(n − 1, d) is a prefix of f(n, d). So: f(n, d) = (f(n−1, d)*10 + d)%X
- Discover the utmost worth of n for which f(n, d) = 0.
- Select the one with the utmost d among the many ones with the utmost n.
Under is the implementation of the above method.
C++
|
|
Time Complexity: O(Y)
Auxiliary House: O(1)
