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.

The key observation is that this is fundamentally a counting problem, not a search problem. We do not need to generate every number and check it. Instead, we can count how many k-digit numbers have all unique digits for each valid k, and sum those counts up. This shifts the problem from brute force enumeration to combinatorics.

Notice that the constraint n <= 8 is extremely small. This means even an exponential approach would work, but it also hints that there is likely a clean mathematical formula since we only have 10 possible digits (0 through 9) and at most 8 digit positions to fill.

Key Constraints:

Intuition

The most straightforward approach: iterate through every number from 0 to 10^n - 1 and check whether it has all unique digits. To check uniqueness, we can extract each digit and use a set to detect duplicates.

This is simple to implement and easy to reason about. For small n (like 0, 1, or 2), it works perfectly fine. But as n grows, the number of candidates grows exponentially (10^n), so this becomes impractical for larger values.

Algorithm

a. Check if all digits of i are unique (use a boolean array or set of size 10).

b. If all digits are unique, increment count.

Example Walkthrough

Code

The brute force works but checks every single number individually. Since we only need to count them, not find them, we can use the structure of digit positions to calculate the answer directly.

Intuition

Instead of checking each number, let us count directly. The key insight is to think about how many numbers of exactly k digits have all unique digits, then sum across all digit lengths from 0 to n.

For a single digit (k = 1), all 10 digits (0 through 9) are valid. That gives us 10 numbers with unique digits.

For exactly 2-digit numbers (10 through 99), the first digit has 9 choices (1 through 9, since leading zeros are not allowed). The second digit has 9 choices (0 through 9 minus whatever we picked for the first digit). 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.

See the pattern? For k-digit numbers with unique digits:

The total count of numbers with unique digits up to n digits is: 1 (for zero) + 9 (for 1-digit) + 99 (for 2-digit) + 99*8 (for 3-digit) + ...

Algorithm

a. Multiply uniqueDigits by availableDigits.

b. Add uniqueDigits to result.

c. Decrement availableDigits by 1.

Example Walkthrough

Code

The combinatorial approach gives us the optimal O(n) solution. But there is another way to think about this problem using backtracking, which is more flexible and extends to harder variants.

Intuition

There is another way to think about this problem that is useful for interview discussions: backtracking. We build numbers digit by digit, keeping track of which digits we have already used. At each position, we try all digits that have not been used yet.

This approach is more general and can be adapted to variants of the problem (like counting unique-digit numbers within an arbitrary range, not just [0, 10^n)). It also demonstrates recursion and backtracking skills, which interviewers value.

The idea is simple: start from an empty number and try appending each unused digit. For the first digit, we can use 1 through 9 (to avoid leading zeros for multi-digit numbers). For subsequent digits, we can use any digit from 0 through 9 that has not been used. Each valid partial number we build is counted.

Algorithm

a. Mark d as used.

b. Recursively try to extend the number by appending unused digits.

c. At each recursive step, increment count and try all unused digits for the next position.

d. Stop when the number reaches n digits.

e. Unmark d (backtrack).

Example Walkthrough

Code