Last Updated: 7 Apr, 2021
Monotone Increasing Digits
Moderate
Asked in company
You are given a non-negative integer ‘N’. Your task is to find the largest number that is less than or equal to ‘N’ with monotone increasing digits.
Note:
An integer has a monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
For example:
Given ‘N’ = 987
The answer is 899 because that is the greatest monotone increasing number possible that is less than ‘N’.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and the only line of each test case contains a single integer ‘N’.
Output format:
For each test case, print a single line containing a single integer denoting the maximum monotone number less than or equal to the given number.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 9
Where ‘T’ is the total number of test cases, and 'N’ is the number given to us.
Time limit: 1 sec.
Approaches
The main idea is to try all possible combinations of numbers that are less than or equal to the given number ‘N’ and pick the greatest possible number.
- Convert ‘N’ into string ‘S’.
- Maintain a string ‘ANS’ and bool ‘CONTINUED’.
- A pointer to the beginning of ‘S’, ‘I’ = 0.
- While ‘I’ is less than ‘S’ length:
- For the current character in ‘S’, we will try to create a string ‘T’, such that it is the greatest possible string if we fix the ‘I’th character of the string.
- ‘T’ = ans + repeat(‘D’,’S’length - ‘I’).
- ‘REPEAT’ is a helper function that:
- Takes a character and a size as input parameters.
- Return a string ‘REPEATEDSTRING’ which is of the size given in the parameter and only contains the given character.
- If ‘T’ is greater than ‘S’, then we add ‘D’ - 1 to the ‘I’ place, which makes ‘T’ less than ‘S.’
- After exiting the loop, ‘ANS’ contains the final string.
- Convert ‘ANS’ into an integer ‘RES’.
- Return ‘RES’ as the final answer.
The main idea is to find the first point where the ‘i’th digit is greater than the ‘i+1’th digit and reduce the ‘i’th digit by 1 and all the rest should be set to 9.
- Convert the number into a string ‘S’.
- Traverse the string and find the first index where ‘S’[i] > ‘S’[i+1].
- Set the ‘S’[i] to ‘S’[i] - 1.
- Traverse from ‘I’ + 1 to the length of the string and set all the digits to ‘9’.
- Convert the string to the number ‘RES’.
- Return ‘RES’ as the result.