Objective: Given a number N, find the largest number which is less than equal to N and has monotone increasing digits.

Monotone Increasing Digits – If all the pairs (x, y) of adjacent digits satisfy the property, x<=y. In other words if all digits are in ascending order (can have duplicates) then digits are called monotone increasing digits.

Example:

N = 324
Output: 299
N = 4321
Output: 3999
N = 12345
Output: 12345

Approach:

Iterate the number from right to left (in reverse order).

Find the last pair of adjacent digits (x, y) where x > y and store the index of x.

In original number, put x-1 at the stored index and put 9 all the indexes at the right of the array.

See the example below for more understanding.

N = 7384
pair 8, 4 8 > 4, stored index= 2
pair 3, 8 3 < 8, no change, stored index = 2
pair 7, 3 7 > 3, stored index = 0
Output = 7 – 1 at the index 0 and put 9 at all the places at right => 6999
___________________________________________________________
N = 391
pair 9, 1 9 > 1, stored index = 1
pair 3, 9 3 < 9, no change in stored index
Output: 9 – 1 at the index 1 and put 9 at all the places at right => 389

Complete Code:

Output:

N = 7384 monotone increasing: 6999
N = 1234 monotone increasing: 1234
N = 1111 monotone increasing: 1111
N = 4321 monotone increasing: 3999

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________