Count Numbers with Unique Digits: Combinatorics with Digit DP

LeetCode Count Numbers with Unique Digits (Problem 357) gives you a non-negative integer n and asks you to count all numbers x where x is at least 0 and less than 10^n that have no repeated digits. For example, 14 has unique digits but 11 does not. The answer for n=2 is 91.

The brute-force instinct is to iterate over every number from 0 up to 10^n - 1 and check each one for repeated digits. That works for small n, but 10^n grows fast. For n=10 you would be checking ten billion numbers. The smarter path is to count directly, without visiting individual numbers at all.

The counting argument

Instead of checking numbers one by one, think about how many ways you can fill the digit slots of a k-digit number without repeating any digit.

For a k-digit number:

• The first digit has 9 choices. It can be anything from 1 to 9. Zero is excluded because that would make it a (k-1)-digit number, not a k-digit one.
• The second digit has 9 choices. It can be anything from 0 to 9 except whatever you picked for the first digit.
• The third digit has 8 choices. It can be anything from 0 to 9 except the two digits already used.
• Each subsequent digit has one fewer choice than the last.

So the count of k-digit numbers with all unique digits is:

count_k = 9 × 9 × 8 × 7 × ... × (11 - k)

The total answer is 1 (for the number 0) plus the sum of count_k for k from 1 to n.

One important boundary: once k is greater than 10, there are no unique-digit numbers at all, because there are only 10 distinct digits (0 through 9). You cannot fill more than 10 slots without repeating. The loop below handles this naturally.

The code

def countNumbersWithUniqueDigits(n: int) -> int:
    if n == 0:
        return 1
    result = 10
    available = 9
    cur = 9
    for _ in range(n - 1):
        cur *= available
        result += cur
        available -= 1
    return result

The variables:

• result starts at 10 because for n >= 1 we already know there are 10 single-digit numbers with unique digits (0 through 9): the base case 1 plus count_1 = 9 equals 10.
• cur tracks the product for the current k. It starts at 9 (the count for k=1).
• available starts at 9 and decrements each iteration. It represents how many unused digits remain for the next slot. After the first digit (9 choices) and the second digit (9 choices), the third slot has 8, the fourth has 7, and so on.

Each loop iteration multiplies cur by the next available count, adds that to result, and then decrements available for the following slot.

Step-by-step walkthrough

Here is the full trace for n=3:

After the loop, result holds the count of all numbers from 0 to 999 with unique digits.

Complexity

The loop runs at most n - 1 times, but since unique digits max out at 10 digits, it effectively runs at most 9 times regardless of how large n is. Space is constant: just three integer variables.

Building blocks

This problem is an instance of permutation counting with decreasing choices. Each time you place a digit, the pool of available digits shrinks by one. That pattern shows up whenever you are counting arrangements without replacement.

The first digit is the special case. Every other slot follows the same rule (subtract one from the pool), but the first slot excludes zero to prevent leading zeros. Once you notice that structure, the product formula writes itself.

You can think of it as: 9 ways to pick the first digit, then a permutation of the remaining k-1 slots drawn from the remaining 9 digits. That is 9 × P(9, k-1) where P(n, r) = n! / (n-r)!.

Edge cases

• n=0: The only number in range is 0 itself. Return 1. The code handles this with an explicit early return before any arithmetic.
• n=1: Numbers 0 through 9 all have unique digits (each is a single digit by definition). The answer is 10. The code initializes result = 10 and the loop runs zero times.
• n greater than 10: There are only 10 distinct digits, so no number can have more than 10 unique digits. Once available reaches 0, cur becomes 0 and adding zero no longer changes result. The answer stops growing at the n=10 value without any special case needed.

From understanding to recall

The insight that unlocks this problem is the reframing: you are not counting numbers, you are counting ways to fill slots. Once you see the slot structure, the product formula is immediate. The first slot has 9 choices (no leading zeros). Each subsequent slot has one fewer choice than the last. Multiply them together.

That reframing is what spaced repetition helps you lock in. The mechanics of the code are not hard, but arriving at the right mental model under pressure is the real skill. When you revisit this problem at increasing intervals, you are practicing the moment of recognition, not just the implementation.

The descending-pool pattern also connects to other problems that count arrangements. Recognizing it here means you will spot it faster in new contexts.

Related posts

• Counting Bits - Another count-based DP problem over integers
• Perfect Squares - Iterative DP accumulation for a counting problem
• House Robber - The pattern of building up a result by iterating over increasing sizes