LeetCode 357 - Count Numbers with Unique Digits

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Backtracking

Solution

Problem Understanding

The problem asks us to count how many integers in the range 0 <= x < 10^n contain no repeated digits.

For example, when n = 2, the valid range is:

0 <= x < 100

This means we consider every number from 0 to 99. Among these numbers, we only count those whose digits are all unique. Numbers like 11, 22, and 99 are excluded because they repeat a digit.

The phrase "unique digits" means that no digit appears more than once within the same number. Leading zeros are not considered actual digits of the number. For instance:

7 is valid
10 is valid
98 is valid
11 is invalid
100 is invalid because 0 repeats

The input n represents the maximum number of digits we are allowed to use. The output is the total count of numbers with unique digits in the range [0, 10^n).

The constraints are:

0 <= n <= 8

This is important because it tells us the maximum digit length is only 8. Since decimal digits only range from 0 to 9, there are only 10 possible unique digits total. This strongly suggests a combinatorial counting approach rather than brute force enumeration.

Several edge cases are important:

n = 0
The range becomes 0 <= x < 1
Only the number 0 exists, so the answer is 1
n > 10
Not relevant here because the constraint limits n <= 8
Still, conceptually, no number longer than 10 digits can have all unique decimal digits
Numbers with leading zeros
We do not explicitly represent leading zeros
For example, 0012 is just 12

A naive implementation that checks every number individually would work for small n, but it becomes inefficient as the range grows exponentially.

Approaches

Brute Force Approach

The brute force method iterates through every number in the range:

0 to 10^n - 1

For each number, we examine its digits and determine whether any digit appears more than once.

One simple way to do this is:

Convert the number to a string
Insert each digit into a set
Compare the set size with the string length

If both lengths match, all digits are unique.

This approach is correct because it explicitly checks every valid candidate and directly verifies the uniqueness condition.

However, it becomes inefficient because the number of integers grows exponentially with n.

For example:

n = 8
Range size = 10^8 = 100,000,000

Checking one hundred million numbers is unnecessarily expensive for such a small combinatorial problem.

Optimal Approach

The key insight is that we do not need to generate the numbers themselves. Instead, we can count how many valid numbers exist for each digit length.

Suppose we want to count valid 2 digit numbers:

First digit:
Cannot be 0
Has 9 choices (1-9)
Second digit:
Cannot repeat the first digit
Has 9 remaining choices

Total:

9 * 9 = 81

For 3 digit numbers:

First digit: 9 choices
Second digit: 9 choices
Third digit: 8 choices

Total:

9 * 9 * 8 = 648

This becomes a permutation counting problem.

We then sum the counts for all lengths from 1 to n, plus the special case 0.

This approach avoids enumeration entirely and runs in constant time relative to the constraint bounds.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^n * n)	O(n)	Checks every number individually
Optimal	O(n)	O(1)	Uses combinatorial counting

Algorithm Walkthrough

Optimal Counting Algorithm

Handle the special case where n == 0.

If n = 0, the only valid number is 0, so we immediately return 1. 2. Initialize the answer for single digit numbers.

All one digit numbers are valid because no digit can repeat within a single digit number.

These are:

0, 1, 2, ..., 9

So we start with:

total = 10

Start counting numbers with more digits.

For 2 digit numbers:

First digit cannot be zero
Remaining digits cannot repeat previous digits

We use:

current_count

to store how many valid numbers exist for the current digit length. 4. Compute counts incrementally.

For digit length k:

First digit has 9 choices
Second digit has 9 remaining choices
Third digit has 8 remaining choices
Fourth digit has 7 remaining choices
And so on

We repeatedly multiply by the remaining available digits. 5. Add each digit length contribution to the total.

After computing all valid numbers for a specific digit length, we add them to the running answer. 6. Continue until reaching digit length n.

Since there are only 10 unique digits, the multiplication naturally decreases as digit length increases.

Why it works

The algorithm works because every valid number with unique digits can be uniquely categorized by its digit length.

For each length:

The first digit cannot be zero
Every subsequent digit must be different from all previously chosen digits

The multiplication principle correctly counts all possible valid arrangements without duplication or omission. Summing these counts across all lengths gives the total number of unique digit numbers in the required range.

Python Solution

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1

        total = 10
        current_count = 9
        available_digits = 9

        for digit_length in range(2, n + 1):
            current_count *= available_digits
            total += current_count
            available_digits -= 1

        return total

The implementation begins by handling the edge case n == 0.

We then initialize:

total = 10
Represents all valid one digit numbers
current_count = 9
Represents the number of valid choices for the first digit of multi digit numbers
available_digits = 9
After choosing the first digit, there are 9 unused digits remaining

Inside the loop:

current_count *= available_digits

expands the count for the next digit position.

For example:

2 digit numbers:
9 * 9
3 digit numbers:
9 * 9 * 8
4 digit numbers:
9 * 9 * 8 * 7

Each iteration adds the newly computed count into total.

The loop continues until we process all digit lengths up to n.

Go Solution

func countNumbersWithUniqueDigits(n int) int {
    if n == 0 {
        return 1
    }

    total := 10
    currentCount := 9
    availableDigits := 9

    for digitLength := 2; digitLength <= n; digitLength++ {
        currentCount *= availableDigits
        total += currentCount
        availableDigits--
    }

    return total
}

The Go implementation follows the same combinatorial logic as the Python solution.

A few Go-specific details are worth noting:

Integer arithmetic is straightforward because the results remain small within the problem constraints.
No additional data structures are required.
Variable naming mirrors the Python version for clarity and consistency.

Worked Examples

Example 1

Input: n = 2

We count all unique digit numbers from 0 to 99.

Initial state:

Variable	Value
total	10
current_count	9
available_digits	9

The initial 10 accounts for:

0-9

Now process 2 digit numbers.

Step	Calculation	Result
current_count *= available_digits	9 * 9	81
total += current_count	10 + 81	91
available_digits -= 1	9 - 1	8

Final answer:

This excludes:

11, 22, 33, ..., 99

Example 2

Input: n = 0

The valid range is:

0 <= x < 1

Only the number 0 exists.

The algorithm immediately returns:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One loop from 2 to n
Space	O(1)	Only constant extra variables are used

The algorithm performs a constant amount of work per digit length. Since n <= 8, the runtime is extremely small.

No auxiliary data structures proportional to input size are required, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.countNumbersWithUniqueDigits(0) == 1      # only number 0
assert solution.countNumbersWithUniqueDigits(1) == 10     # digits 0-9
assert solution.countNumbersWithUniqueDigits(2) == 91     # standard example
assert solution.countNumbersWithUniqueDigits(3) == 739    # three digit counting
assert solution.countNumbersWithUniqueDigits(4) == 5275   # larger combinatorial case
assert solution.countNumbersWithUniqueDigits(5) == 32491  # verifies continued multiplication
assert solution.countNumbersWithUniqueDigits(6) == 168571 # larger valid range
assert solution.countNumbersWithUniqueDigits(7) == 712891 # near upper bound
assert solution.countNumbersWithUniqueDigits(8) == 2345851 # maximum constraint

Test	Why
`n = 0`	Validates the special edge case
`n = 1`	Verifies single digit initialization
`n = 2`	Matches provided example
`n = 3`	Tests multi step multiplication
`n = 4`	Verifies continued combinatorial growth
`n = 5`	Confirms correctness for larger values
`n = 6`	Stress test with more iterations
`n = 7`	Near upper constraint
`n = 8`	Maximum allowed input

Edge Cases

Edge Case 1: `n = 0`

This case is easy to mishandle because many implementations assume at least one digit exists.

However, the problem defines the range as:

0 <= x < 10^0

Since 10^0 = 1, only the number 0 is included.

The implementation handles this explicitly with:

if n == 0:
    return 1

Edge Case 2: Maximum Constraint `n = 8`

A brute force solution becomes extremely inefficient at this scale because it would require checking up to:

100,000,000

numbers individually.

The combinatorial solution avoids enumeration entirely and computes the result using only a few multiplications, making it efficient even at the maximum input size.

Edge Case 3: Running Out of Digits

There are only 10 decimal digits total.

As digit length increases, the number of available unused digits decreases:

9, 8, 7, ...

The algorithm correctly tracks remaining choices using:

available_digits -= 1

This guarantees we never count invalid numbers with repeated digits.