357. Count Numbers with Unique Digits
mediumCount non-negative integers below 10^n whose decimal representations have all distinct digits. A combinatorial DP with a clean closed-form per digit length.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10^n.
Constraints
0 <= n <= 8
Examples
Example 1
n = 291Explanation: 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
n = 01Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Count by exact digit length k from 1 to n and add 1 for the number 0.
Hint 2
For length k there are 9 choices for the leading digit and 9, 8, 7, ... choices for the subsequent digits.
Hint 3
Sum 9 * 9 * 8 * ... over k = 1..n and add 1 for zero.
Solution approach
Reveal approach
Count by exact digit length k. For length 1 there are 10 unique-digit numbers (0..9). For length k > 1 the leading digit has 9 choices (1..9) and each subsequent position has progressively one fewer choice: 9, 8, 7, etc. So the count for length k is 9 * 9 * 8 * ... * (11 - k). Total = 1 + sum over k from 1 to min(n, 10) of those products (start with 1 to include 0). For n >= 10 the count saturates because you cannot have more than 10 unique decimal digits. Iterative accumulation in O(n) time, O(1) space.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- dynamic-programming
- combinatorics
- math
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill Count Numbers with Unique Digits and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →