Free lesson · DSA Mastery - Interview Prep, End to End

Count Numbers with Unique Digits

Hard7 min readdsadynamic-programming

Count Numbers with Unique Digits

Count Numbers with Unique Digits is the simplest Digit DP: count integers in [0, 10^n - 1] all of whose digits are distinct. The DP defines dp[pos][tight][usedMask][started] where usedMask is a 10-bit bitmask of digits already in the number. At each position, choose any digit c not yet in usedMask. Memoize on untight states. It demonstrates the bitmask constraint state within Digit DP and shows how the framework handles "no repeated digits" properties cleanly. We present the combinatorial closed-form (canonical) and the general Digit DP (alternative - needed if the upper bound changes from 10^n to arbitrary N).

The insight: a number with all unique digits has at most 10 digits (only digits 0-9). For numbers with exactly k digits (with no leading zero requirement, since we're counting in [0, 10^n - 1] and the problem treats 0 as having 0 digits or 1 digit depending on convention), the count factors cleanly: 9 choices for the first digit (1-9), 9 for the second (0-9 minus the first), 8 for the third (0-9 minus the first two), and so on. So the count of k-digit unique-digit numbers is 9 · 9 · 8 · 7 · ... · (11 - k). Summing over k from 1 to n (plus 1 for the number 0) gives the answer.

The Problem

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10^n.

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.
That's 100 - 9 = 91.

Example 2:

Input:  n = 0
Output: 1

Explanation: Only 0 is in [0, 10^0 - 1] = [0, 0]; 0 has unique digits trivially.

Constraints:

0 <= n <= 8.

Approaches Overview

#	Approach	Time	Space	Verdict
1	Closed-form combinatorial counting	O(n)	O(1)	Canonical
2	Digit DP with bitmask of used digits	O(n · 2 · 2^10)	O(n · 2^10)	Alternative

Closed-form: total = 1 (for number 0) + 9 · 9 · 8 · ... summed across digit counts 1 to n. The closed form leverages the simplicity of the bound (10^n - 1 is "every digit position can be 0-9").

Digit DP: works for arbitrary upper bound. State = (pos, tight, usedMask, started). For each position, pick a digit not in usedMask, update state. This is overkill for this problem but transfers directly to "count unique-digit numbers in [0, N]" for arbitrary N.

Approach 1: Closed-Form Combinatorial Counting - Canonical

The Idea

For each number of digits k from 1 to n, count the k-digit unique-digit numbers:

1st digit: 9 choices (1-9; can't be 0 for a "true" k-digit number).
2nd digit: 9 choices (0-9 minus the first).
3rd digit: 8 choices.
... and so on, down to (11 - k) choices for the k-th digit.

Sum these counts, then add 1 for the number 0.

Logic Flowchart

graph TD
    A["if n == 0 return 1"] --> B["total = 10 (k=1 case: 0-9 all unique)"]
    B --> C["countForLengthK = 9; availableDigits = 9"]
    C --> D["for k from 2 to n:"]
    D --> E["countForLengthK *= availableDigits"]
    E --> F["total += countForLengthK"]
    F --> G["availableDigits--"]
    G --> D
    D --> H["return total"]

    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the closed-form Count Unique Digit Numbers: accumulate counts across digit lengths one through n, with each length contributing a product of declining digit choices.

Code

public static int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int total = 10;                                                       // k=1: numbers 0-9
    int countForLengthK = 9;                                              // running count for length k (starts at k=1: 9 non-zero choices)
    int availableDigits = 9;                                              // remaining digit choices for next position
    for (int k = 2; k <= n; k++) {
        countForLengthK *= availableDigits;                               // multiply in next-position's choices
        total += countForLengthK;
        availableDigits--;
    }
    return total;
}

// Usage:
// countNumbersWithUniqueDigits(2) -> 91
// countNumbersWithUniqueDigits(0) -> 1
// countNumbersWithUniqueDigits(3) -> 739

This Java code computes the count of unique-digit numbers with a closed-form accumulation across digit lengths.

Step-by-Step Walkthrough

Tracing countNumbersWithUniqueDigits(2):

graph LR
    F0["n=2: total=10 (k=1, numbers 0-9); countForLengthK=9; availableDigits=9"]
    F1["k=2: countForLengthK = 9 * 9 = 81 (first digit 1-9, second digit any of 9 remaining)"]
    F2["total += 81 → total = 91; availableDigits-- → 8 (for next iteration)"]
    F3["loop ends; return 91"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough computes 91 for n equals two: ten single-digit unique numbers plus eighty-one two-digit unique numbers.

Result: 91.

Complexity

Time: O(n). Space: O(1).

Approach 2: Digit DP with Bitmask of Used Digits - Alternative

The Idea

For arbitrary upper bounds (not just 10^n - 1), use the standard Digit DP framework with a 10-bit mask tracking which digits are already used.

Code

public static int countUniqueDigitsUpToN(int N) {
    String digits = Integer.toString(N);
    int n = digits.length();
    int[] d = new int[n];
    for (int i = 0; i < n; i++) d[i] = digits.charAt(i) - '0';
    Integer[][][] memo = new Integer[n][1 << 10][2];
    return solve(d, 0, 0, true, false, memo);
}

private static int solve(int[] d, int pos, int usedMask, boolean tight, boolean started, Integer[][][] memo) {
    if (pos == d.length) return started ? 1 : 0;
    if (!tight && memo[pos][usedMask][started ? 1 : 0] != null)
        return memo[pos][usedMask][started ? 1 : 0];
    int total = 0;
    int maxDigit = tight ? d[pos] : 9;
    for (int c = 0; c <= maxDigit; c++) {
        if (!started && c == 0) {
            total += solve(d, pos + 1, usedMask, tight && c == maxDigit, false, memo);
        } else {
            if ((usedMask & (1 << c)) != 0) continue;
            total += solve(d, pos + 1, usedMask | (1 << c), tight && c == maxDigit, true, memo);
        }
    }
    if (!tight) memo[pos][usedMask][started ? 1 : 0] = total;
    return total;
}

// Usage: countUniqueDigitsUpToN(100) -> 91 (excluding 100 itself which has duplicate digit "no, 100 has digits 1, 0, 0 - not unique")

This Java code implements the general Digit DP with a 10-bit usedMask and a started flag, memoized on untight states.

Complexity

Time: O(n · 2 · 1024). Space: O(n · 1024).

Complexity Comparison

Approach	Time	Space	Key Idea
Closed-form combinatorial	O(n)	O(1)	factorial-like product over digit choices
Digit DP with bitmask	O(n · 2^10)	O(n · 2^10)	general framework for arbitrary upper bounds

For this problem (bound = 10^n - 1), the closed-form is optimal. For variant problems with arbitrary N, the Digit DP is needed. Both approaches use the same mathematical insight (declining digit choices); the DP just generalizes the iteration.

Variations & Follow-ups

Why is the closed-form so much simpler than Digit DP?

The upper bound 10^n - 1 has the property "every digit position can be 0-9 freely" - meaning the tight flag is always false past the first position (or there's no tight constraint at all because every digit is at its max). The Digit DP collapses to the closed-form when the bound is "all 9s." The general principle: Digit DP becomes a closed-form combinatorial formula when the upper bound has a simple digit structure (all 9s, all 0s, or a specific pattern). Recognizing this saves implementation time. For arbitrary bounds, fall back to the full DP.

How does the DP handle the `started` flag?

Numbers like 005 should be counted as 5 (one digit), not 005 (three digits). The started flag tracks whether the first non-zero digit has been placed. Before starting (leading zeros), the digit doesn't add to usedMask. Once started, all digits add to the mask. The general lesson: Digit DPs that distinguish "k-digit number" from "padded representation" use a started flag to skip leading zeros. This is one of the most common boilerplate additions in Digit DP.

What about the bound n=10?

For n ≥ 10, all 10-digit numbers must use at least one repeated digit (pigeonhole: 10 positions, 10 digit options - but only 9 first-digit options because of the no-leading-zero requirement, ensuring at least one repeat in 11-or-more digit numbers). So for n ≥ 10, the answer caps at f(10) = total k-digit unique-digit numbers for k = 0..10. The problem's constraint n ≤ 8 keeps things in the simple regime.

How does this extend to "exactly k unique digits"?

A variant: count numbers ≤ N where exactly k digit values appear (not just "unique"). The DP state extends with popcount(usedMask) or the mask itself. The structure stays the same. The general principle: Digit DP constraint dimensions extend naturally - add the dimension to the state, update transitions accordingly. This is the "extensibility" that makes Digit DP universal.

What about edge cases?

n = 0: Only the number 0 is in [0, 10^0 - 1] = [0, 0]; answer 1.
n = 1: All of 0-9 are unique-digit numbers; answer 10.
n = 11: Same as n=10 (no 11-digit number has all unique digits).

Common Interview Pitfalls

Forgetting the n=0 base case. Special-case it before the loop.
Off-by-one in the running product. Carefully manage the multiplication sequence so the per-iteration count is correct (init to 9, multiply by 9 first, then 8, then 7, ...).
Confusing "count unique-digit numbers" with "count distinct digits in a number." Different problems; the former counts numbers, the latter counts digits within one number.
In the DP, treating leading zeros as digits. Must skip via the started flag.

Why This Topic Matters

Count Numbers with Unique Digits is the gentlest introduction to Digit DP. For the specific bound 10^n - 1, a closed-form combinatorial formula suffices - demonstrating that Digit DP collapses to closed forms when the bound has a simple structure. For arbitrary upper bounds, the full Digit DP framework with bitmask state and started flag is the canonical solution. The pattern - bitmask constraint state within Digit DP - recurs in any "no repeated digits" or "specific digit set" problem.

The next topic, Number of Digit One, is a digit-occurrence counting Digit DP: count the total number of times the digit 1 appears across all numbers in [1, N]. Unlike most Digit DPs (which count numbers satisfying a property), this counts occurrences - a subtle but important shift. The DP defines dp[pos][tight][onesSoFar] and returns the sum of onesSoFar across all valid full numbers, weighted by their count. It demonstrates the occurrence-summing variant of Digit DP and shows that the framework handles aggregate counts as cleanly as binary-property counts.

Back to DSA Mastery - Interview Prep, End to End

Count Numbers with Unique Digits

Count Numbers with Unique Digits

The Problem

Approaches Overview

Approach 1: Closed-Form Combinatorial Counting - Canonical

The Idea

Logic Flowchart

Code

Step-by-Step Walkthrough

Complexity

Approach 2: Digit DP with Bitmask of Used Digits - Alternative

The Idea

Code

Complexity

Complexity Comparison

Variations & Follow-ups

Why is the closed-form so much simpler than Digit DP?

How does the DP handle the started flag?

What about the bound n=10?

How does this extend to "exactly k unique digits"?

What about edge cases?

Common Interview Pitfalls

Why This Topic Matters

How does the DP handle the `started` flag?