Count Non-Decreasing Digit Numbers

Problem

Count the positive integers from 1 through n whose decimal digits are non-decreasing from left to right, so each digit is at least the one before it.

Use digit DP with the position, last digit, a tight flag for matching the prefix of n, and a started flag that ignores leading zeros before the first digit. Assume n >= 1.

Hint

Leading zeros must not count as a first digit, so a started flag is required.

Test cases

case 1

in: [10]

expected: 9

case 2

in: [20]

expected: 18

case 3

in: [100]

expected: 54

case 4

in: [200]

expected: 99

case 5

in: [1000]

expected: 219

Starter codePython

def count_non_decreasing_digits(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor