AlgoMaster Logo

Count Numbers with Unique Digits

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to count how many integers in the range [0, 10^n) have all distinct digits. For example, 123 has unique digits but 112 does not because the digit 1 repeats.

This is a counting problem, not a search problem. We do not need to generate every number and test it. Numbers can be grouped by digit length: if we know how many k-digit numbers have all unique digits for each k from 1 to n, summing those counts (plus 1 for the number 0) gives the answer without examining a single candidate.

There are only 10 distinct digits, so any number with more than 10 digits must repeat one. With at most 8 digit positions to fill from a pool of 10 digits, the count per position follows a fixed product, which is what the direct formula exploits.

Key Constraints:

  • 0 <= n <= 8 → The range tops out at [0, 10^8), which is 100 million candidates. Enumerating and checking all of them is borderline at this size, and each check costs another factor of n for the digit scan. A combinatorial count over digit positions runs in O(n) instead.
  • n can be 0 → The range is [0, 1), which contains only the number 0, so the answer is 1.

Approach 1: Brute Force (Check Every Number)

Intuition

Iterate through every number from 0 to 10^n - 1 and check whether it has all unique digits. To check uniqueness, extract the digits one at a time with repeated division by 10 and record each in a boolean array of size 10; seeing a digit twice rejects the number.

For small n (0, 1, or 2) this finishes quickly. But the number of candidates grows by a factor of 10 with each increment of n, so the running time is exponential in n.

Algorithm

  1. If n is 0, return 1.
  2. Initialize a counter count = 0.
  3. For each number i from 0 to 10^n - 1:
    • Check if all digits of i are unique (use a boolean array or set of size 10).
    • If all digits are unique, increment count.
  4. Return count.

Example Walkthrough

1n=2, range=[0, 100). Check each number for unique digits.
0
11
1
22
2
33
3
44
4
55
5
66
6
77
7
88
8
99
1/5

Code

The brute force checks every number individually. Since the task asks for a count rather than the numbers themselves, the digit positions can be counted directly.

Approach 2: Dynamic Programming (Combinatorial Counting)

Intuition

Instead of checking each number, count how many numbers of exactly k digits have all unique digits, then sum across digit lengths. Every number in the range has exactly one digit length, so these groups are disjoint and together cover all of [0, 10^n). Summing their counts gives the answer.

For a single digit (k = 1), all 10 values (0 through 9) qualify.

For exactly 2-digit numbers (10 through 99), the first digit has 9 choices (1 through 9, since a leading zero would make it a 1-digit number). The second digit has 9 choices (0 through 9 minus whatever the first digit was). So there are 9 * 9 = 81 two-digit numbers with unique digits.

For exactly 3-digit numbers, the first digit has 9 choices, the second has 9 choices, and the third has 8 choices (10 total digits minus the 2 already used). That is 9 9 8 = 648.

The same product continues for any k:

  • First digit: 9 choices (cannot be 0)
  • Second digit: 9 choices (can be 0, but cannot repeat the first)
  • Third digit: 8 choices
  • Fourth digit: 7 choices
  • ...
  • k-th digit: (11 - k) choices

The total up to n digits is 10 (all single-digit numbers, including 0) + 99 (2-digit) + 99*8 (3-digit) + ... Each term is the previous term times the next factor, so a single loop that keeps a running product computes the whole sum.

Algorithm

  1. If n is 0, return 1.
  2. Start with result = 10. Every number from 0 to 9 has unique digits.
  3. Set uniqueDigits = 9, the count of 1-digit numbers with a nonzero leading digit (1 through 9). Only these can be extended to longer numbers, since a multi-digit number cannot start with 0.
  4. Set availableDigits = 9, the unused digits remaining for the next position.
  5. For each digit length k from 2 to n:
    • Multiply uniqueDigits by availableDigits. The product is now the count of exactly-k-digit numbers with unique digits.
    • Add uniqueDigits to result.
    • Decrement availableDigits by 1.
  6. Return result.

Example Walkthrough

1n=3. Tally per digit length. Index 0 holds the number 0 by itself; index 1 holds the nine numbers 1-9
0
1
0-digit
1
9
1-digit
2
0
3
0
1/5

Code

The combinatorial count is already optimal at O(n). Backtracking solves the same problem by explicit construction, and the technique extends to variants the closed-form product cannot handle.

Approach 3: Backtracking

Intuition

Build numbers digit by digit, tracking which digits are already used. The first digit ranges over 1 through 9, since a multi-digit number cannot start with 0. Each later position ranges over the digits 0 through 9 that are still unused. Every partial number built this way is a complete valid number in its own right (the prefix 3, 8 is the number 38), so the count is incremented at every node of the recursion tree, not only at depth n. The number 0 is the one value this construction cannot produce, so it is counted separately up front.

The construction visits each unique-digit number exactly once: a number's digit sequence determines a single path through the recursion tree, and no two numbers share a full path. Counting visited nodes therefore counts the numbers themselves, with no risk of double counting.

This approach does more work than the formula, but it adapts to variants the formula does not cover, such as counting unique-digit numbers below an arbitrary upper bound rather than a power of 10.

Algorithm

  1. Start with count = 1 to account for the number 0.
  2. For each starting digit d from 1 to 9:
    • Mark d as used and increment count, which counts the single-digit number d.
    • Recursively extend the number: for each unused digit, mark it, increment count, recurse one level deeper, then unmark it.
    • Stop extending when the number reaches n digits.
    • Unmark d before moving to the next starting digit.
  3. Return count.

Example Walkthrough

1n=2. count=1 for the number 0. Mark first digit 1 as used, count=2
0
false
1
true
used
2
false
3
false
4
false
5
false
6
false
7
false
8
false
9
false
1/5

Code