Count Numbers with Unique Digits

Count Numbers with Unique Digits

What is this problem about?

Given an integer $n$, you need to count all numbers $x$ such that $0 \le x < 10^n$ and $x$ has all unique digits. For example, if $n=2$, you are looking at numbers from 0 to 99. Numbers like 11, 22, and 33 are excluded because they have repeated digits.

Why is this asked in interviews?

Google and Bloomberg ask this to test basic combinatorial counting and the ability to handle edge cases. It requires you to understand how to build a number digit by digit and how the number of available choices decreases as you use more digits. It’s also an excellent introductory problem for "Digit DP" or backtracking.

Algorithmic pattern used

The primary pattern is Combinatorics / Permutations.

1. For $n=0$: Only one number (0).
2. For $n=1$: Numbers 0-9 (10 unique).
3. For $n=2$:
   • One-digit numbers: 10 (0-9).
   • Two-digit numbers: The first digit has 9 choices (1-9), the second digit has 9 choices (0-9, excluding the first digit). Total = $9 imes 9 = 81$.
   • Total = $10 + 81 = 91$.
4. For $n=k$: The $k$-th digit has $(10 - (k-1))$ choices.

Example explanation

Let $n = 3$.

• 1-digit: 10
• 2-digit: $9 imes 9 = 81$
• 3-digit: $9 imes 9 imes 8 = 648$ Total: $10 + 81 + 648 = 739$. The logic is: 9 choices for the first digit (cannot be 0), 9 for the second (can be 0, but not the first), 8 for the third, and so on.

Common mistakes candidates make

A common error is including numbers with leading zeros as unique (e.g., counting "012" as a unique 3-digit number). In this problem, "012" is just the number 12, which is already counted in the 2-digit category. Another mistake is not stopping at $n=10$, as any number with more than 10 digits must have at least one repeated digit.

Interview preparation tip

For counting problems based on digits, first try a simple combinatorial approach. If the conditions are more complex (e.g., "count unique digits between $L$ and $R$"), move to the "Digit DP" template.