DSA problem
Count Numbers with Unique Digits
Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10^n. A number has unique digits if every digit appears at most once in its decimal representation.
For n = 0 the range is [0, 1), which contains only the value 0, so the answer is 1. For n = 1 every single-digit number (0 through 9) trivially has unique digits, so the answer is 10. For larger n, the count grows by adding all unique-digit numbers of length exactly k for k = 2, 3, ..., n.
A brute-force solution enumerates every integer in [0, 10^n) and checks whether its digit-set has the same size as its length. This is correct but costs O(10^n * n) time and quickly becomes infeasible for n beyond 8 or 9. The structural observation needed is that for k >= 2, a unique-digit number with exactly k digits is built by choosing an ordered sequence of k distinct digits where the leading digit is non-zero.
The optimal combinatorial formula counts length-k unique-digit numbers as 9 * 9 * 8 * 7 * ... * (11 - k): 9 choices for the first digit (1-9), 9 remaining choices for the second (0-9 minus the first), 8 for the third, and so on. Summing those products from k = 1 up to min(n, 10) and adding 1 for the number 0 gives the answer in O(n) time and O(1) space. Beyond k = 10 no further unique-digit numbers exist because the alphabet of decimal digits is exhausted.
Examples
n = 291n = 01n = 3739Constraints
- 0 <= n <= 8
- The answer fits in a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.