DSA Digit DP

Digit DP counts numbers up to a bound by building their digits one place at a time. Its key state is a flag that says whether the prefix still matches the bound.

The tight flag in action

The bound is 25. A first digit of 2 stays tight, and a first digit of 1 turns loose.

bound = '25'
for first in ['1', '2']:
    tight = first == bound[0]
    limit = int(bound[1]) if tight else 9
    print('first', first, 'tight', tight, 'next digit up to', limit)

Brute force at a small bound

Brute force tests every number directly. It is slow but needs no clever state.

def has_repeat(x):
    s = str(x)
    return len(set(s)) != len(s)
count = sum(1 for x in range(31) if not has_repeat(x))
print('no repeat up to 30:', count)

Leading zeros stay unused

A leading zero starts no digit and marks nothing as used. The first real digit starts the number and sets its bit.

started = False
used = 0
for d in [0, 0, 5, 5]:
    if not started and d == 0:
        print(d, 'still not started')
        continue
    started = True
    print(d, 'repeat' if used & (1 << d) else 'new digit')
    used = used | (1 << d)

Example

from functools import lru_cache

def count_digit_dp(limit):
    digits = [int(c) for c in str(limit)]
    @lru_cache(maxsize=None)
    def go(pos, tight, started, used):
        if pos == len(digits):
            return 1
        top = digits[pos] if tight else 9
        total = 0
        for d in range(top + 1):
            ntight = tight and d == top
            if not started and d == 0:
                total += go(pos + 1, ntight, False, 0)
            elif used & (1 << d):
                continue
            else:
                total += go(pos + 1, ntight, True, used | (1 << d))
        return total
    return go(0, True, False, 0)

def count_brute(limit):
    total = 0
    for x in range(limit + 1):
        s = str(x)
        if len(set(s)) == len(s):
            total += 1
    return total

for limit in (30, 100, 250):
    fast = count_digit_dp(limit)
    slow = count_brute(limit)
    print(limit, 'digit dp', fast, 'brute', slow, 'match', fast == slow)

Key points

A tight flag is true while the built prefix equals the bound prefix
A loose prefix may place any digit from zero to nine next
A started flag ignores leading zeros when a property is checked
The property here is that no digit repeats inside the number
Brute force checks each number one by one at small bounds

In this example, the digit method counts numbers whose digits never repeat. The number zero counts as valid, because a single digit cannot repeat. Brute force checks every number up to the same bound. The two counts match at all three bounds, which verifies the state design.

Note

Memoisation works on loose states because the bound no longer matters there

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

from functools import lru_cache

def count_digit_dp(limit):
    digits = [int(c) for c in str(limit)]
    @lru_cache(maxsize=None)
    def go(pos, tight, started, used):
        if pos == len(digits):
            return 1
        top = digits[pos] if tight else 9
        total = 0
        for d in range(top + 1):
            ntight = tight and d == top
            if not started and d == 0:
                total += go(pos + 1, ntight, False, 0)
            elif used & (1 << d):
                continue
            else:
                total += go(pos + 1, ntight, True, used | (1 << d))
        return total
    return go(0, True, False, 0)

def count_brute(limit):
    total = 0
    for x in range(limit + 1):
        s = str(x)
        if len(set(s)) == len(s):
            total += 1
    return total

for limit in (30, 100, 250):
    fast = count_digit_dp(limit)
    slow = count_brute(limit)
    print(limit, 'digit dp', fast, 'brute', slow, 'match', fast == slow)

Exercise

What does a tight flag value of true mean?

The number is already below the bound The prefix still equals the bound prefix No digit has repeated yet Leading zeros are still being placed