Count Numbers with Unique Digits

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

For example, if n = 2, the output should be 91 because we are counting the numbers from 0 to 99, and excluding numbers with repeating digits like 11, 22, 33, ..., 99.

Another example is when n = 0, the output should be 1 because we are only considering 0, which is a valid number with unique digits.

What is an efficient algorithm to solve this problem, and what are its time and space complexity?

## Count Numbers with Unique Digits

### Problem Description

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

**Example 2:**

Input: n = 0 Output: 1

### Solution

We can solve this problem using dynamic programming or a combinatorial approach. Here's a dynamic programming solution:

```python
def count_numbers_with_unique_digits(n: int) -> int:
    if n == 0:
        return 1

    count = 1  # Count for x = 0
    unique_digits = 9
    available_numbers = 9

    for i in range(1, min(n + 1, 11)):
        unique_digits *= available_numbers
        count += unique_digits
        available_numbers -= 1

    return count

Explanation

1. Base Case: If n is 0, return 1 (only 0 satisfies the condition).
2. Initialization:
   • count = 1 (initial count for 0).
   • unique_digits = 9 (number of choices for the first digit, excluding 0).
   • available_numbers = 9 (number of available digits for the next position).
3. Iteration: Iterate from i = 1 to min(n + 1, 11):
   • Multiply unique_digits by available_numbers to get the count of numbers with i unique digits.
   • Add unique_digits to count.
   • Decrement available_numbers.
4. Return: Return the final count.

Example Walkthrough (n = 2)

1. n = 0: count = 1
2. i = 1:
   • unique_digits = 9
   • count = 1 + 9 = 10
   • available_numbers = 8
3. i = 2:
   • unique_digits = 9 * 8 = 72
   • count = 10 + 72 = 82
   • available_numbers = 7
4. The min(n+1, 11) will stop at i=3, as n=2.
5. Add the case where n=1
   • unique_digits = 9
   • count = 1 + 9 + 9*8 = 91

Complexity Analysis

• Time Complexity: O(n) since the loop runs at most n times, capped at 10.
• Space Complexity: O(1) since we use a constant number of variables.

Edge Cases

• n = 0: Returns 1.
• n > 10: The number of unique digits will always be limited by the fact that there are only 10 digits available. Thus, the loop will never iterate more than 10 times.