Code Implementation

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        count = 10
        uniqueDigits = 9
        availableNumber = 9
        for i in range(2, n+1):
            uniqueDigits *= availableNumber
            count += uniqueDigits
            availableNumber -= 1
            if availableNumber == 0:
                break
        return count
      

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int count = 10, uniqueDigits = 9, availableNumber = 9;
        for (int i = 2; i <= n; ++i) {
            uniqueDigits *= availableNumber;
            count += uniqueDigits;
            --availableNumber;
            if (availableNumber == 0) break;
        }
        return count;
    }
};
      

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int count = 10, uniqueDigits = 9, availableNumber = 9;
        for (int i = 2; i <= n; ++i) {
            uniqueDigits *= availableNumber;
            count += uniqueDigits;
            availableNumber--;
            if (availableNumber == 0) break;
        }
        return count;
    }
}
      

var countNumbersWithUniqueDigits = function(n) {
    if (n === 0) return 1;
    let count = 10, uniqueDigits = 9, availableNumber = 9;
    for (let i = 2; i <= n; ++i) {
        uniqueDigits *= availableNumber;
        count += uniqueDigits;
        availableNumber--;
        if (availableNumber === 0) break;
    }
    return count;
};
      

Problem Description

You are given a non-negative integer n. Your task is to count how many numbers with unique digits exist in the range [0, 10n). In other words, for each integer x such that 0 ≤ x < 10n, count it if and only if every digit in x is distinct (no digit repeats).

• For example, if n = 2, you should count all numbers from 0 to 99 with no repeated digits (e.g., 11 is invalid).
• Constraints: 0 ≤ n ≤ 8.
• Leading zeros are allowed (e.g., 01 is counted as 1).

Thought Process

The first idea that comes to mind is brute-forcing through all numbers from 0 to 10n - 1 and checking if each number has unique digits. While this works for small n, it quickly becomes infeasible for large n because the number of possibilities grows exponentially.

Instead, we realize that the problem is about counting, not generating, so we can use combinatorics. For each possible number length (from 1 up to n), we can count how many numbers of that length have all unique digits. We sum those counts to get the final answer.

The key insight is that for each digit position, we must pick a digit that hasn't been used yet. For example, the first digit can't be zero (except for the number zero itself), and each subsequent digit must be different from the previous ones.

Solution Approach

• Base Case: If n = 0, the only valid number is 0, so the answer is 1.
• Count for 1-digit numbers: There are 10 numbers (from 0 to 9), all with unique digits.
• For numbers with more digits:
  • For 2-digit numbers: The first digit can be 1-9 (9 choices), the second digit can be any of the remaining 9 digits (including 0, but not the first digit), so 9 * 9 = 81.
  • For 3-digit numbers: First digit (9 options), second digit (9 options), third digit (8 options), so 9 * 9 * 8 = 648.
  • This pattern continues, each time reducing the available digits by 1 for each additional digit.
• Implementation:
  1. Initialize count = 10 for n ≥ 1.
  2. For each digit length from 2 to n:
     • Multiply the number of available digits for each position.
     • Add the result to count.
  3. Stop when there are no more digits to choose from (after 10 digits, all digits are used).

This approach leverages permutations and avoids brute-force enumeration, making it efficient even for larger n.

Example Walkthrough

Let's walk through the process for n = 2:

• 1-digit numbers: There are 10 numbers: 0 to 9.
• 2-digit numbers:
  • First digit: 1-9 (9 choices).
  • Second digit: 0-9 except the first digit (9 choices).
  • Total: 9 * 9 = 81
• Total count: 10 + 81 = 91
• Explanation: All numbers from 0 to 99 are considered. Numbers like 11, 22, etc., are not counted because they repeat digits.

Time and Space Complexity

• Brute-force approach: For each number in [0, 10^n), check if its digits are unique. This is O(10^n * n), which becomes infeasible quickly as n increases.
• Optimized combinatorial approach: We only loop up to n (at most 8), and for each, perform a constant number of multiplications. So the time complexity is O(n).
• Space complexity: Both approaches use O(1) extra space (no large data structures).

Summary

The problem asks for the count of numbers with all unique digits in the range [0, 10^n). While brute-force is possible for small n, leveraging combinatorics provides a much more efficient solution. By counting the number of ways to build numbers of each length with unique digits, we avoid unnecessary computation. The approach is elegant because it uses mathematical reasoning over enumeration, making it both efficient and easy to implement.