Medium

Count Numbers With Non-Decreasing Digits

LAB

Return how many integers from 0 through n have digits that never decrease from left to right.

EXAMPLES

Example 1

Input
{
  "n": 135
}

Output
91

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

Standard digit DP with last_digit constraint. Digits must be >= previous digit.

Reveal reference solution +

pythonREFERENCE

def countNumbers(self, l: str, r: str) -> int:
    MOD = 10 ** 9 + 7

    def count(s):
        n = len(s)

        @cache
        def dp(i, tight, started, last_digit):
            if i == n:
                return 1 if started else 0

            limit = int(s[i]) if tight else 9
            res = 0

            start = last_digit if started else 0
            for d in range(start, limit + 1):
                new_tight = tight and (d == limit)
                new_started = started or (d > 0)
                new_last = d if new_started else 0
                res = (res + dp(i + 1, new_tight, new_started, new_last)) % MOD

            return res

        return dp(0, True, False, 0)

    def subtract_one(s):
        s = list(s)
        i = len(s) - 1
        while i >= 0 and s[i] == '0':
            s[i] = '9'
            i -= 1
        s[i] = str(int(s[i]) - 1)
        return ''.join(s).lstrip('0') or '0'

    return (count(r) - count(subtract_one(l)) + MOD) % MOD

TimeO(n × 10)

SpaceO(n × 10)

Open on LeetCode ↗