LeetCode 357: Count Numbers with Unique Digits

Problem Restatement

Given an integer n, count how many integers x satisfy:

0 <= x < 10**n

and have no repeated digits.

A number has unique digits if every digit appears at most once.

Examples:

123 has unique digits
102 has unique digits
11 does not have unique digits
100 does not have unique digits

The range includes 0.

The range does not include 10^n.

The problem constraints are 0 <= n <= 8. The official examples include n = 2, whose answer is 91, and n = 0, whose answer is 1.

Input and Output

Example function shape:

def countNumbersWithUniqueDigits(n: int) -> int:
    ...

Examples

For:

n = 0

The range is:

0 <= x < 1

Only the number 0 is included.

So the answer is:

1

For:

n = 1

The range is:

0 <= x < 10

The numbers are:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

All have unique digits.

So the answer is:

10

For:

n = 2

The range is:

0 <= x < 100

There are 100 numbers from 0 to 99.

The repeated-digit two-digit numbers are:

11, 22, 33, 44, 55, 66, 77, 88, 99

There are 9 of them.

So the answer is:

100 - 9 = 91

First Thought: Check Every Number

A direct solution is to loop through every number from 0 to 10^n - 1.

For each number:

1. Convert it to a string.
2. Check whether all characters are distinct.
3. Count it if no digit repeats.

Example:

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        limit = 10 ** n
        count = 0

        for x in range(limit):
            digits = str(x)

            if len(set(digits)) == len(digits):
                count += 1

        return count

This is easy to understand.

But it checks every number, so the time grows as 10^n.

For n = 8, that means checking 100,000,000 numbers.

We need to count directly instead.

Key Insight

Count valid numbers by their digit length.

For length 0, we count the number 0.

For length 1, the valid numbers are:

0 through 9

There are 10.

For length 2, the first digit cannot be 0.

So:

So length 2 contributes:

9 * 9 = 81

For length 3:

So length 3 contributes:

9 * 9 * 8

In general, for a fixed length k >= 1:

first digit: 9 choices
second digit: 9 choices
third digit: 8 choices
fourth digit: 7 choices
...

Then add counts for all lengths from 1 to n, plus the number 0.

Algorithm

If n == 0, return 1.

Otherwise:

1. Start with total = 10, which counts all one-digit numbers: 0 through 9.
2. Let current = 9, representing the count for the current length before adding the next digit.
3. Let available = 9, representing how many choices remain for the next digit.
4. For every length from 2 to n:
   • Update:

current *= available

• Add current to total.
• Decrease available.

5. Return total.

Since there are only 10 digits, lengths above 10 contribute nothing. For this problem, n <= 8, so this does not affect the official constraints.

Correctness

Every number in the range 0 <= x < 10^n has at most n digits.

The algorithm counts valid numbers by exact digit length.

The number 0 is included in the one-digit count.

For every length k >= 1, the first digit has 9 choices because it cannot be 0. Each later position must use a digit that has not appeared before. Therefore the number of valid k-digit numbers is counted by multiplying the number of choices at each position.

These length groups are disjoint because a number has exactly one decimal length, except 0, which is already included in the base count.

The algorithm sums the counts for all lengths up to n, so it counts every valid number in the required range exactly once.

Therefore, the returned value is correct.

Complexity

With n <= 8, this is constant in practice.

Implementation

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

        total = 10
        current = 9
        available = 9

        for length in range(2, n + 1):
            current *= available
            total += current
            available -= 1

        return total

Code Explanation

The case n = 0 means the range is only:

0 <= x < 1

So only 0 is counted:

if n == 0:
    return 1

For n >= 1, all one-digit numbers are valid:

total = 10

The variable current stores how many valid numbers have the current length.

Before length 2, we start with:

current = 9

This represents the first digit choices: 1 through 9.

The next digit has 9 choices:

available = 9

For each new length:

current *= available

This adds one more digit position.

Then:

total += current

adds all valid numbers of that length.

Finally:

available -= 1

because one more digit has been used.

Testing

def run_tests():
    s = Solution()

    assert s.countNumbersWithUniqueDigits(0) == 1
    assert s.countNumbersWithUniqueDigits(1) == 10
    assert s.countNumbersWithUniqueDigits(2) == 91
    assert s.countNumbersWithUniqueDigits(3) == 739
    assert s.countNumbersWithUniqueDigits(4) == 5275
    assert s.countNumbersWithUniqueDigits(8) == 2345851

    print("all tests passed")

run_tests()

Test meaning: