Monotone Increasing Digits Problem


Description

LeetCode Problem 738.

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

Example 1:

1
2
Input: n = 10
Output: 9

Example 2:

1
2
Input: n = 1234
Output: 1234

Example 3:

1
2
Input: n = 332
Output: 299

Constraints:

  • 0 <= n <= 10^9


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string n_str = to_string(N);
        
        int marker = n_str.size();
        for (int i = n_str.size()-1; i > 0; i --) {
            if (n_str[i] < n_str[i-1]) {
                marker = i;
                n_str[i-1] = n_str[i-1]-1;
            }
        }
        
        for (int i = marker; i < n_str.size(); i ++) 
            n_str[i] = '9';
        
        return stoi(n_str);
    }
};




Related Posts

Three Equal Parts Problem

LeetCode 927. You are given an array arr which consists...

Surface Area Of 3D Shapes Problem

LeetCode 892. You are given an n x n grid...

Super Palindromes Problem

LeetCode 906. Let’s say a positive integer is a super-palindrome...

Smallest Range I Problem

LeetCode 908. You are given an integer array nums and...

Projection Area Of 3D Shapes Problem

LeetCode 883. You are given an n x n grid...

Prime Palindrome Problem

LeetCode 866. Given an integer n, return the smallest prime...