MediumMathDynamic ProgrammingBacktracking

Count Numbers with Unique Digits

1 approach, code in every language

Given an integer `n`, count how many integers `x` in the range `0 <= x < 10^n` have all distinct digits, meaning no digit appears more than once in `x`.

Return that count. Note that single-digit numbers, including `0`, always qualify because they contain only one digit.

Example 1

Input: n = 2

Output: 91

Every value from 0 to 99 counts except the nine repeated-digit numbers 11, 22, 33, 44, 55, 66, 77, 88, and 99, leaving 100 - 9 = 91.

Example 2

Input: n = 0

Output: 1

The only integer with 0 <= x < 10^0 = 1 is 0 itself, which trivially has unique digits.

Constraints

0 <= n <= 8

Combinatorics by Digit Length

Count qualifying numbers separately for each digit length using the multiplication principle, then sum the results.

Loading animation…

Intuition

Instead of testing individual numbers, count how many valid numbers exist at each possible length. The single value `0` is handled once at the start. For a number with exactly `L` digits, the leading digit has nine choices (any digit except zero), the next digit has nine remaining choices (any digit except the one used, and zero is now allowed), then eight, then seven, and so on as digits get consumed. Multiplying these choices gives the count of unique-digit numbers of that exact length. Because there are only ten distinct digits, no valid number can be longer than ten digits, so we cap the length at `min(n, 10)`. Summing the count over every length up to that cap, plus the initial one for zero, yields the answer.

Algorithm walkthrough

1Handle the trivial case `n = 0` by returning 1, since only 0 lies in the range.
2Start a running total at 1 to account for the number 0.
3Cap the maximum digit length at `min(n, 10)` because digits cannot repeat beyond ten places.
4For each length from 1 to the cap, begin the count at 9 for the non-zero leading digit.
5Multiply by the shrinking pool of remaining digits (9, then 8, and so on) for each additional place in that length.
6Add every per-length count to the running total and return it.

Implementation

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        total = 1
        limit = min(n, 10)
        for length in range(1, limit + 1):
            count = 9
            available = 9
            for _ in range(length - 1):
                count *= available
                available -= 1
            total += count
        return total

Time

O(n)

Space

O(1)

The work is bounded by a double loop that runs at most 10 times total because digit length is capped at 10. Only a few scalar variables are used.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Clean Crate Stamps is our own problem on the technique behind Count Numbers with Unique Digits: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free