Skip to main content

357. Count Numbers with Unique Digits

medium

Count 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 Sam K., 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

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

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

More DP 1D practice problems

See all DP 1D problems →