Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.
Example 1:
Input: n = 2 Output: 91 Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99
Example 2:
Input: n = 0 Output: 1
Constraints:
0 <= n <= 8Problem 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.
This approach involves using backtracking to explore all possible numbers up to 10^n and counting those numbers which have all unique digits. It recursively builds numbers digit by digit, ensuring that no digit repeats.
This Python solution uses a recursive backtracking strategy. The function backtrack attempts to construct a number digit by digit. It maintains a bitmask used to track digits that are already used. For each position, it checks available digits and proceeds if they are unique. The subtraction by one at the end accounts for the extra count due to the starting zero.
Python
JavaScript
Time Complexity: O(10^n), since it explores all possible combinations.
Space Complexity: O(n), due to the recursive stack space.
This approach calculates the number of numbers with unique digits using permutations directly. For each number length, it computes how many unique numbers can be formed by choosing different digits, starting with 9 choices for the first digit and reducing the choices as digits get used.
This C++ solution uses a mathematical approach by computing permutations for each length from 1 to n. Starting with an initial condition where 0 can be used, it iteratively calculates unique combinations by considering different initial starting points and choices for remaining digits without repetition.
Time Complexity: O(n), since it iterates through each number length.
Space Complexity: O(1), as it uses a fixed amount of extra space.
This problem essentially asks for the number of numbers in the given range [l, ..r] that satisfy certain conditions. The conditions are related to the composition of the numbers rather than their size, so we can use the concept of Digit DP to solve it. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, ..r] problem, we generally convert it to the problem of [1, ..r] and then subtract the result of [1, ..l - 1], i.e.:
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
However, for this problem, we only need to find the value for the range [1, ..10^n-1].
Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.
Based on the problem information, we design a function dfs(i, mask, lead), where:
represents the current position being searched, starting from the highest digit, i.e., i = 0 represents the highest digit. represents the current state of the number, i.e., the j-th bit of mask being 1 indicates that the digit j has been used. indicates whether the current number only contains leading 0s.The function executes as follows:
If i exceeds the length of the number n, i.e., i < 0, it means the search is over, directly return 1.
Otherwise, we enumerate the digits j from 0 to 9 for the position i. For each j:
-th bit of mask is 1, it means the digit j has been used, so we skip it. is true and j = 0, it means the current number only contains leading 0s. When we recurse to the next level, lead remains true.-th bit of mask to 1, and set lead to false.Finally, we sum all the results from the recursive calls to the next level, which is the answer.
The answer is dfs(n - 1, 0, True).
The time complexity is O(n times 2^D times D), and the space complexity is O(n times 2^D). Here, n is the length of the number n, and D = 10$.
Similar Problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(10^n), since it explores all possible combinations. |
| Mathematical Permutations Approach | Time Complexity: O(n), since it iterates through each number length. |
| State Compression + Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(10!) | O(10) | Useful for understanding the constraint and generating actual numbers with unique digits |
| Mathematical Permutations | O(n) | O(1) | Best approach for interviews and large inputs since it counts valid permutations directly |
357. Count Numbers with Unique Digits Leetcode Medium Google Microsoft Interview Simple Question • Code with Alisha • 14,019 views views
Watch 9 more video solutions →Practice Count Numbers with Unique Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor