Count Numbers with Unique Digits

Intuition

Instead of testing individual numbers, count how many valid numbers exist at each possible length. The single value `0` is handled once at the start. For a number with exactly `L` digits, the leading digit has nine choices (any digit except zero), the next digit has nine remaining choices (any digit except the one used, and zero is now allowed), then eight, then seven, and so on as digits get consumed. Multiplying these choices gives the count of unique-digit numbers of that exact length. Because there are only ten distinct digits, no valid number can be longer than ten digits, so we cap the length at `min(n, 10)`. Summing the count over every length up to that cap, plus the initial one for zero, yields the answer.

Algorithm walkthrough

1. 1Handle the trivial case `n = 0` by returning 1, since only 0 lies in the range.
2. 2Start a running total at 1 to account for the number 0.
3. 3Cap the maximum digit length at `min(n, 10)` because digits cannot repeat beyond ten places.
4. 4For each length from 1 to the cap, begin the count at 9 for the non-zero leading digit.
5. 5Multiply by the shrinking pool of remaining digits (9, then 8, and so on) for each additional place in that length.
6. 6Add every per-length count to the running total and return it.

Implementation

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        total = 1
        limit = min(n, 10)
        for length in range(1, limit + 1):
            count = 9
            available = 9
            for _ in range(length - 1):
                count *= available
                available -= 1
            total += count
        return total