Monotone Increasing Digits - Leetcode Solution

Problem Statement:

Given a non-negative integer n, find the largest number that is less than or equal to n with monotone increasing digits.

A number is monotone increasing if every digit in the number is greater than or equal to the previous digit.

Example:

Input: 10 Output: 9

Input: 1234 Output: 1234

Input: 332 Output: 299

Solution:

We can solve this problem by first converting the given number n into an array of digits. Then, we can iterate through the array from right to left, checking if each digit is greater than the previous digit. If it is not, then we can set all the subsequent digits to 9 and decrement the current digit by 1.

This process will ensure that the resulting number is monotone increasing and less than or equal to n.

Let's look at a step-by-step implementation of this approach:

1. Convert the given number n into an array of digits.

digits = [] while n: digits.append(n % 10) n //= 10 digits.reverse()

2. Iterate through the array from right to left and modify digits accordingly.

for i in range(len(digits) - 1, 0, -1): if digits[i - 1] > digits[i]: digits[i - 1] -= 1 # decrement the current digit for j in range(i, len(digits)): digits[j] = 9 # set subsequent digits to 9

3. Convert the modified array of digits back into a number and return it.

result = 0 for digit in digits: result = result * 10 + digit return result

Let's test the solution with the examples given in the problem statement:

Example 1:

Input: 10 Output: 9

digits = [1, 0] i = 1 -> digits[0] > digits[1], so decrement digits[0] and set digits[1] to 9 digits = [0, 9] result = 9

Example 2:

Input: 1234 Output: 1234

digits = [1, 2, 3, 4] i = 3 -> digits[2] < digits[3], nothing to modify i = 2 -> digits[1] < digits[2], nothing to modify i = 1 -> digits[0] < digits[1], nothing to modify result = 1234

Example 3:

Input: 332 Output: 299

digits = [3, 3, 2] i = 2 -> digits[1] > digits[2], decrement digits[1] and set digits[2] to 9 digits = [3, 2, 9] i = 1 -> digits[0] > digits[1], decrement digits[0] and set digits[1:] to 9 digits = [2, 9, 9] result = 299

Therefore, the solution of this problem is to iterate through the array of digits, modify it in place and convert it back to a number.

1