Count Numbers with Unique Digits - Video Solutions

Problem Overview: Given an integer n, count how many numbers x satisfy 0 ≤ x < 10^n where every digit in x is unique. Leading zeros are allowed when forming shorter numbers, but digits within a number cannot repeat.

Approach 1: Backtracking Enumeration (Time: O(10!), Space: O(10))

This approach builds numbers digit by digit using backtracking. Start with each possible first digit and recursively append digits that have not been used yet. Maintain a boolean array or set to track which digits are already used. Every time you extend a number, increment the count because any prefix with unique digits is valid. The recursion stops once the length reaches n or all digits are used.

The key idea is simple: explore all valid digit combinations while preventing duplicates through a visited structure. Because there are only 10 digits, the search space is bounded and manageable. This method mirrors how you'd generate permutations with constraints, making it useful for understanding the structure of the problem and verifying results for small n.

Approach 2: Mathematical Permutations (Time: O(n), Space: O(1))

The optimal solution observes that the task is purely combinatorial. For numbers with unique digits, each position must choose a digit that hasn't been used before. For length k, the first digit has 9 options (1–9), the second has 9 options (including 0 but excluding the first digit), the third has 8, and so on. This forms a decreasing permutation sequence.

Compute counts for each length from 1 to n and sum them. For example: length 1 → 10 numbers (0–9). Length 2 → 9 × 9. Length 3 → 9 × 9 × 8. Continue multiplying by the remaining available digits. Since there are only 10 unique digits, calculations stop once n exceeds 10. This approach relies on basic math and permutation logic and can also be viewed as a compact form of dynamic programming where each step depends on the previous count.

The insight is recognizing that generating every number is unnecessary. Instead, count the number of valid permutations directly.

Recommended for interviews: The mathematical permutation approach is what interviewers expect. It reduces the problem to simple combinatorics and runs in O(n) time with constant space. Backtracking shows you understand the constraint of unique digits and can systematically generate possibilities, but the permutation formula demonstrates stronger problem‑solving and optimization skills.