Count Numbers with Unique Digits
Problem
n, count the integers x with
0 ≤ x < 10n whose decimal digits are all different
(e.g. 907 counts, 404 does not).n=2Output91 (all of 0..99 except 11,22,...,99)n=0Output1 (only 0)n=3Output7390 ≤ n ≤ 8
Try it yourself
class Solution {
public int countNumbersWithUniqueDigits(int n) {
}
}
k-digit number (k ≥ 2) has 9 choices for the
leading digit (no 0), then 9, 8, 7, … for the rest, so
count(k) = 9 · 9 · 8 ·…· (11-k); add the
10 one-digit numbers.Instinct Count numbers in [L, R] (R up to 10^9 or 10^18) whose digits obey a rule - build the number digit by digit with a "still tight to N" flag.
Memory hack Walk the digits on a leash - stay tight to N or break free, and once free you never go back. Remember PTLS - Position, Tight, Leading zero, State.
Open the Digit DP guide →Approaches
Brute ForceCheck Every Number
O(10n · n)Space O(1)Loop over every x below 10n and peel its
digits with % 10, using a 10-bit mask to detect a repeat.
public int countNumbersWithUniqueDigits(int n) { int limit = 1; for (int i = 0; i < n; i++) limit *= 10; int count = 0; for (int x = 0; x < limit; x++) if (allDistinct(x)) count++; return count; } private boolean allDistinct(int x) { int seen = 0; // bit d set = digit d already used do { int d = x % 10; if ((seen >> d & 1) == 1) return false; seen |= 1 << d; x /= 10; } while (x > 0); return true; }
Trivially right, but 108 numbers at n = 8 is painfully slow.
BetterBacktracking: Build Only Valid Numbers
O(answer)Space O(n)Instead of testing numbers, generate them: extend a prefix one digit at a time, choosing only unused digits (no leading 0). Every node of the search tree is a distinct valid number, so the work equals the answer (~2.3M at n = 8) rather than 10n.
public int countNumbersWithUniqueDigits(int n) { return 1 + extend(0, 0, n); // 1 for the number 0 itself } // numbers formed by appending at least one digit to the current prefix private int extend(int len, int used, int n) { if (len == n) return 0; int count = 0; for (int d = (len == 0 ? 1 : 0); d <= 9; d++) { if ((used >> d & 1) == 1) continue; count += 1 + extend(len + 1, used | 1 << d, n); } return count; }
Skips all invalid numbers, but still visits each valid one individually.
OptimalProduct Rule per Length
O(n)Space O(1)Sum the count for each length. Length 1 gives 10 (0..9). For length
k, multiply the previous length's “nonzero-leading” count by
11 - k, the digits still unused. Beyond 10 digits the count is 0, so
the loop is capped.
public int countNumbersWithUniqueDigits(int n) { if (n == 0) return 1; int total = 10; // 0..9 int ways = 9; // 1-digit numbers with a non-zero leading digit for (int k = 2; k <= Math.min(n, 10); k++) { ways *= 11 - k; // digits still unused for the k-th position total += ways; } return total; }
A handful of multiplications — pure counting, no enumeration.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Check Every Number | O(10n · n) | O(1) |
| Better | Backtracking: Build Only Valid Numbers | O(answer) | O(n) |
| Optimal | Product Rule per Length | O(n) | O(1) |
- Allowing 0 as the leading digit — that double-counts shorter numbers.
- Forgetting the number
0itself (answer for n = 0 is 1, not 0). - Letting the product run past 10 digits; it must become 0 (pigeonhole).
- Start with brute force to confirm small answers (n = 2 → 91).
- Explain the leading-digit choice (9) vs later choices (9, 8, 7, …).
- Mention this is the warm-up for digit DP problems with an upper bound (e.g. 1012).