Monotone Increasing Digits

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
2 upvotes
Asked in companies
Tata Consultancy Services (TCS)SAP Labs

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
789
987

Sample Output 1:

789
899

Explanation of the Sample Input 1:

For the first test case:
The answer is 789 because that is the greatest monotone increasing number possible that is equal to ‘N’.

For the second test case:
The answer is 899 because that is the greatest monotone increasing number possible.

Sample Input 2:

2
10
11

Sample Output 2:

9
11
Hint

Can we try all possible combinations?

Approaches (2)
Try all possible combinations

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.
Time Complexity

O(log(N) * log(N)), where ‘N’ is the number given.

 

Since we are trying all possible digits and there at most ‘log(N)’ digits and each comparison take log(N) time, therefore O(log(N) * log(N)).

Space Complexity

O(log (N)), where 'N' is the number given.


Since we are using a string to store the digits of the numbers.

Code Solution
(100% EXP penalty)
Monotone Increasing Digits
Full screen
Console