Count Numbers with Unique Digits — Problem & Solution
Count Numbers with Unique Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Numbers with Unique Digits is a medium coding problem on dynamic programming, math and backtracking, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Backtracking
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return the count of numbers x with 0 <= x < 10^n that have all distinct digits.
Example 1
Input: n = 2
Output: 91
Explanation: All 100 numbers below 100 except the nine repdigits 11, 22, …, 99.
Example 2
Input: n = 0
Output: 1
Explanation: Only x = 0 satisfies 0 <= x < 1.
Example 3
Input: n = 3
Output: 739
Constraints
0 <= n <= 8
Hints for Count Numbers with Unique Digits
Hint 1
Count by digit length and add the counts up.
Hint 2
A number with exactly
ddigits has 9 choices for the leading digit and then 9, 8, 7, … for the rest.Hint 3
Anything past ten digits is impossible — there are only ten distinct digits.
How to solve Count Numbers with Unique Digits
Count by digit length: a d-digit number with distinct digits has 9 · 9 · 8 · … · (11 - d) choices; sum over d up to min(n, 10), plus the ten one-digit numbers.
Approach
- Return 1 for
n = 0. - Start
total = 10,current = 9; fordfrom 2 tomin(n, 10),current *= 11 - dand add it. - Return
total.
Why it works
The leading digit cannot be 0 (9 choices), then each subsequent position avoids all earlier digits. Beyond ten digits no number can have distinct digits.
Complexity
- Time —
O(min(n, 10)) - Space —
O(1)
Pitfalls
- The one-digit count is 10 (including 0), not 9.
Reference solution
Python
def countNumbersWithUniqueDigits(n: int) -> int:
if n == 0:
return 1
total, current = 10, 9
for digits in range(2, min(n, 10) + 1):
current *= 11 - digits
total += current
return totalJava
public static int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int total = 10, current = 9;
for (int digits = 2; digits <= n && digits <= 10; digits++) {
current *= 11 - digits;
total += current;
}
return total;
}C++
int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int total = 10, current = 9;
for (int digits = 2; digits <= n && digits <= 10; digits++) {
current *= 11 - digits;
total += current;
}
return total;
}JavaScript
var countNumbersWithUniqueDigits = function(n) {
if (n === 0) return 1;
let total = 10, current = 9;
for (let digits = 2; digits <= n && digits <= 10; digits++) {
current *= 11 - digits;
total += current;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Backtracking