Count Numbers with Unique Digits solution and explanation
Google
9 more videos on this problem
357. Count Numbers with Unique Digits Leetcode Medium Google Microsoft Interview Simple QuestionCode with Alisha · 12:53 · 14K views
2.f) Count Numbers with Unique Digits || Dynamic ProgrammingKashish Mehndiratta · 14:38 · 6K views
Count numbers with unique digits | Dynamic Programming | Leetcode #357Joey'sTech · 7:19 · 1K views
Dynamic Programming - 3 || LeetCode - count-numbers-with-unique-digits 357Arnabi Mitra · 7:22 · 1K views
Count Numbers with Unique Digits | Problem - 357 |Leetcode problem solvedTechFeline · 5:29 · 833 views
【每日一题】LeetCode 357. Count Numbers with Unique DigitsHuifeng Guan · 8:41 · 590 views
LeetCode 357 | Count Numbers With Unique Digits | Approach & SolutionCarlos · 16:27 · 567 views
Leetcode solving 357 Count Numbers with Unique DigitsMath Geeks · 5:10 · 453 views
Leetcode Question 357 "Count Numbers with Unique Digits" in JavaGhumman Tech · 7:20 · 393 views
#357. Count Numbers with Unique Digits | LeetCode 刷题日记（python）PinkWitch 诸葛筱暖 TV · 6:31 · 342 views
The problem
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 <= 8
Approach overview
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.
Approach 1: Backtracking Approach
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.
def countNumbersWithUniqueDigits(n):
def backtrack(pos, used):
if pos == n:
return 1
count = 1 # Count the number consisting of leading zeros
for digit in range(0 if pos > 0 else 1, 10):
if not (used & (1 << digit)):
count += backtrack(pos + 1, used | (1 << digit))
return count
if n == 0:
return 1
return backtrack(0, 0) - 1function countNumbersWithUniqueDigits(n) {
function backtrack(pos, used) {
if (pos === n) return 1;
let count = 1;
for (let digit = (pos > 0) ? 0 : 1; digit < 10; digit++) {
if ((used & (1 << digit)) === 0) {
count += backtrack(pos + 1, used | (1 << digit));
}
}
return count;
}
if (n === 0) return 1;
return backtrack(0, 0) - 1;
}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.
Time Complexity: O(10^n), since it explores all possible combinations.
Space Complexity: O(n), due to the recursive stack space.
Approach 2: Mathematical Permutations Approach
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.
public class UniqueDigits {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int total = 1;
for (int i = 1; i <= n; i++) {
int uniqueNumbers = 9;
for (int j = 0; j < i - 1; j++) {
uniqueNumbers *= (9 - j);
}
total += uniqueNumbers;
}
return total;
}
}#include <cmath>
int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int total = 1;
int maxNumber = pow(10, n);
for (int i = 1; i <= n; i++) {
int uniqueNumbers = 9;
for (int j = 0; j < i - 1; j++) {
uniqueNumbers *= (9 - j);
}
total += uniqueNumbers;
}
return total;
}This Java solution computes the total number of integers with unique digits up to 10^n by calculating possible configurations of digits. Each iteration considers a new length of numbers from 1 to n and factors in permutations of unused digits to compute the total count of unique numbers.
Time Complexity: O(n), due to the loop that calculates permutations.
Space Complexity: O(1), as the space usage does not grow with input size.
Approach 3: State Compression + Digit DP
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:
- The digit i
represents the current position being searched, starting from the highest digit, i.e.,i = 0represents the highest digit. - The digit mask
represents the current state of the number, i.e., thej-th bit ofmaskbeing1indicates that the digitjhas been used. - The boolean lead
indicates whether the current number only contains leading0s.
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:
- If the j
-th bit ofmaskis1, it means the digitjhas been used, so we skip it. - If lead
is true andj = 0, it means the current number only contains leading0s. When we recurse to the next level,leadremains true. - Otherwise, we recurse to the next level, update the j
-th bit ofmaskto1, and setleadto 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:
function countNumbersWithUniqueDigits(n: number): number {
const f: number[][] = Array.from({ length: n }, () => Array(1 << 10).fill(-1));
const dfs = (i: number, mask: number, lead: boolean): number => {
if (i < 0) {
return 1;
}
if (!lead && f[i][mask] !== -1) {
return f[i][mask];
}
let ans = 0;
for (let j = 0; j < 10; ++j) {
if ((mask >> j) & 1) {
continue;
}
if (lead && j === 0) {
ans += dfs(i - 1, mask, true);
} else {
ans += dfs(i - 1, mask | (1 << j), false);
}
}
if (!lead) {
f[i][mask] = ans;
}
return ans;
};
return dfs(n - 1, 0, true);
}func countNumbersWithUniqueDigits(n int) int {
f := make([][1 << 10]int, n)
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, mask int, lead bool) int
dfs = func(i, mask int, lead bool) int {
if i < 0 {
return 1
}
if !lead && f[i][mask] != -1 {
return f[i][mask]
}
ans := 0
for j := 0; j < 10; j++ {
if mask>>j&1 == 1 {
continue
}
if lead && j == 0 {
ans += dfs(i-1, mask, true)
} else {
ans += dfs(i-1, mask|1<<j, false)
}
}
if !lead {
f[i][mask] = ans
}
return ans
}
return dfs(n-1, 0, true)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(10^n), since it explores all possible combinations. |
| Mathematical Permutations Approach | Time Complexity: O(n), due to the loop that calculates permutations. |
| State Compression + Digit DP | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Numbers with Unique Digits easy or hard?
The problem is rated Medium because the brute force idea is straightforward but recognizing the permutation pattern requires combinatorial reasoning. Once the pattern is identified, the implementation becomes very short and efficient.
How to solve Count Numbers with Unique Digits in O(n)?
Iterate over digit lengths from 1 to n and compute permutations. For length k, the count is 9 × 9 × 8 × ... for k digits because each new digit has fewer choices. Accumulate these counts to get the total number of valid integers.
Count Numbers with Unique Digits Python or Java solution?
Python solutions commonly implement backtracking with a visited set or use a simple loop to compute permutations. Java and C++ implementations often use the mathematical approach with iterative multiplication to maintain O(n) time and O(1) space.
What is the best approach for Count Numbers with Unique Digits?
The mathematical permutation approach is the most efficient. It counts how many valid digit permutations exist for each length instead of generating numbers. This runs in O(n) time with O(1) space and stops after 10 digits because only 10 unique digits exist.
Is Count Numbers with Unique Digits asked at Google/Amazon/Meta?
Permutation and combinatorics counting problems like this appear in interviews at large companies including Google and Amazon. The question tests understanding of digit constraints, permutations, and recognizing when enumeration can be replaced by counting.
What data structure is used in Count Numbers with Unique Digits?
The optimal solution mainly uses mathematical counting and does not require complex data structures. A backtracking implementation typically uses a boolean array or set to track which digits have already been used.
What is the time complexity of Count Numbers with Unique Digits?
The optimal permutation-based solution runs in O(n) time and O(1) space since it only multiplies decreasing digit choices for each length up to n. A backtracking solution can take up to O(10!) time because it explores permutations of digits.