LeetCode 1012: Numbers With Repeated Digits

Problem Restatement

We are given an integer n.

We need to return the count of positive integers up to n (inclusive) that have at least one repeated digit.

The official constraints state that 1 <= n <= 10^9.

Input and Output

Function shape:

def numDupDigitsAtMostN(n: int) -> int:
    ...

Examples

Example 1:

n = 20

Numbers with repeated digits in [1, 20]: 11.

Answer:

1

Example 2:

n = 100

Numbers with repeated digits: 11, 22, 33, ..., 99 (9 numbers).

Answer:

10

Wait: also 100 has no repeated digits (digits 1, 0, 0 → 0 is repeated). So answer is 10.

Key Insight

It is easier to count numbers with no repeated digits and subtract from n.

Count integers in [1, n] with all distinct digits.

This breaks into:

1. All numbers with fewer digits than n (all distinct digits).
2. Numbers with the same number of digits as n but digit-by-digit bounded by n.

Algorithm

Let digits be the list of digits of n.

Let L = len(digits).

Step 1: Count distinct-digit numbers with fewer than L digits.

For a k-digit number (k < L):

• The first digit has 9 choices (1-9).
• The second digit has 9 choices (0-9 minus first).
• The third has 8 choices, etc.

Count = 9 * P(9, k-1) where P(n, k) = n! / (n-k)!.

Step 2: Count distinct-digit numbers with exactly L digits that are <= n.

Walk digit by digit. For each position i:

• Choose a digit d from 0 to digits[i] - 1 (or 1 to digits[i] - 1 for the first).
• d must not be already used.
• The remaining positions can be any of the unused digits.

For each valid prefix smaller than n’s prefix, count permutations of the remaining positions using unused digits.

Sum these up, then subtract from n to get the answer.

Correctness

Every positive integer has either distinct digits or at least one repeated digit.

Counting distinct-digit integers precisely and subtracting from n gives the count of integers with at least one repeated digit.

The digit-by-digit enumeration ensures we count every distinct-digit integer up to n exactly once.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Let L = len(str(n)).

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

from math import perm

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        digits = list(map(int, str(n)))
        L = len(digits)
        count = 0

        # Count distinct-digit numbers with fewer digits
        for k in range(1, L):
            count += 9 * perm(9, k - 1)

        # Count distinct-digit numbers with L digits, <= n
        used = set()
        for i, d in enumerate(digits):
            start = 1 if i == 0 else 0
            for x in range(start, d):
                if x not in used:
                    count += perm(9 - i, L - i - 1)
            if d in used:
                break
            used.add(d)
        else:
            count += 1  # n itself has distinct digits

        return n - count

Code Explanation

Count distinct-digit numbers shorter than n:

for k in range(1, L):
    count += 9 * perm(9, k - 1)

perm(9, k-1) counts ways to fill positions 2 through k from 9 remaining digits.

Walk digit by digit and count valid prefixes:

for x in range(start, d):
    if x not in used:
        count += perm(9 - i, L - i - 1)

For each digit x less than digits[i] (and not already used), we can freely place L - i - 1 more distinct digits.

After the loop, if all prefix digits were distinct (the else branch), n itself is a distinct-digit number:

else:
    count += 1

Finally subtract from n to count numbers with repeated digits:

return n - count

Testing

def run_tests():
    s = Solution()

    assert s.numDupDigitsAtMostN(20) == 1
    assert s.numDupDigitsAtMostN(100) == 10
    assert s.numDupDigitsAtMostN(1000) == 262
    assert s.numDupDigitsAtMostN(1) == 0
    assert s.numDupDigitsAtMostN(11) == 1

    print("all tests passed")

run_tests()