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:

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

Input: n = 0 Output: 1

# Count Numbers with Unique Digits

## Problem Description

Given an integer `n`, we need to find the count of all numbers `x` with unique digits such that `0 <= x < 10^n`.

For example, if `n = 2`, we need to count all numbers between 0 and 99 (inclusive) that have unique digits. This means excluding numbers like 11, 22, 33, ..., 99.

## Naive Approach

A brute-force approach would involve iterating through all numbers from 0 to `10^n - 1` and, for each number, checking if its digits are unique. If the digits are unique, we increment our count. This approach is simple but inefficient, especially for larger values of `n`.

```python
def count_numbers_with_unique_digits_naive(n):
    count = 0
    for i in range(10**n):
        if has_unique_digits(i):
            count += 1
    return count


def has_unique_digits(num):
    digits = str(num)
    return len(set(digits)) == len(digits)

Optimal Approach (Dynamic Programming)

We can use dynamic programming to solve this problem more efficiently.

Let dp[i] be the count of numbers with unique digits of length i. We can derive the following:

• dp[1] = 10 (0 to 9)
• For i > 1, the first digit can be any digit from 1 to 9 (9 choices). The second digit can be any of the remaining 9 digits (including 0), the third digit can be any of the remaining 8 digits, and so on.

So, dp[i] = 9 * 9 * 8 * ... * (10 - i + 1).

The final answer is the sum of dp[i] for i from 1 to n.

def count_numbers_with_unique_digits(n):
    if n == 0:
        return 1
    
    dp = [0] * (n + 1)
    dp[1] = 10
    
    ans = dp[1]
    unique_digits = 9
    available_numbers = 9
    
    for i in range(2, min(n + 1, 11)):
        unique_digits = unique_digits * available_numbers
        dp[i] = unique_digits
        ans += dp[i]
        available_numbers -= 1
        
    return ans

Example

Let's say n = 2:

• dp[1] = 10 (0-9)
• dp[2] = 9 * 9 = 81 (10-98 excluding duplicates like 11, 22, ..., 99)

Total count = dp[1] + dp[2] = 10 + 81 = 91

Big(O) Runtime Analysis

The optimal solution has a time complexity of O(n), where n is the input integer. This is because we iterate from 2 to min(n + 1, 11) in the count_numbers_with_unique_digits function. The number of iterations is directly proportional to n. In each iteration, we perform constant-time operations (multiplication and addition).

Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(n). We use a dp list of size n + 1 to store the counts of numbers with unique digits for lengths 1 to n. This list takes up space proportional to n.

Edge Cases

1. n = 0: The problem states that when n = 0, the output should be 1 (representing the number 0 itself).
2. n > 10: Since there are only 10 unique digits (0-9), any number with length greater than 10 will necessarily have repeated digits. Therefore, for n > 10, the count remains the same as for n = 10. In the provided code, min(n + 1, 11) takes care of this edge case by limiting the loop to a maximum of 10 iterations.