Count Numbers With Unique Digits - Leetcode Solution

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

Example: Input: n = 2 Output: 91 Explanation: The answer is 91 because there are 91 such numbers: 0, 1, 2, …, 8, 9, 10, 12, …, 98.

Solution:

Approach: The approach to solving this problem is to calculate the count of numbers with unique digits for each value of n i.e. for each value of n we will calculate the count of numbers with unique digits from 0 to 10^n. Then we will sum all the counts to get the final count.

Let us first write a brute-force algorithm. We will generate all the numbers from 0 to 10^n and check if the number has unique digits.

Algorithm:

• count = 0
• for i in range(10**n):
  • num_str = str(i)
  • if len(set(num_str)) == len(num_str):
    • count += 1
• return count

This algorithm works perfectly fine for small values of n. However, it is not efficient for larger values of n. The time complexity of this algorithm is O(10^n * n).

So, let us try to come up with a more efficient algorithm.

Observation: The count of numbers with unique digits for n = 0 is 1 (0). The count of numbers with unique digits for n = 1 is 10 (0, 1, 2, …, 9). The count of numbers with unique digits for n = 2 is 91 (0, 1, 2, …, 9, 10, 12, 13, …, 98).

We can observe that the count of numbers with unique digits for n = 2 can be calculated as follows:

• For the first digit, we have 9 choices (1 to 9).
• For the second digit, we have 9 choices again (0 to 9 except the first digit).
• Therefore, the total count is 9 * 9 + 1 (the 1 is for the number 0).

Similarly, the count of numbers with unique digits for n = 3 can be calculated as follows:

• For the first digit, we have 9 choices (1 to 9).
• For the second digit, we have 9 choices again (0 to 9 except the first digit).
• For the third digit, we have 8 choices (0 to 9 except the first two digits).
• Therefore, the total count is 9 * 9 * 8 + 9 * 8 * 7 + 1.

We can generalize this for any value of n.

Algorithm:

• If n == 0, return 1.
• If n == 1, return 10.
• If n > 10, set n = 10 (because for n > 10, the count is the same as n = 10).
• count = 10 # count for n = 1 (0, 1, 2, …, 9)
• unique_digits = 9 # number of unique digits available for the first digit (1 to 9)
• available_digits = 9 # number of available digits for the remaining digits (0 to 9 except the first digit)
• for i in range(2, n + 1):
  • unique_digits *= available_digits
  • count += unique_digits
  • available_digits -= 1
• return count

Let us run this algorithm for n = 2.

• n = 2
• count = 10 # count for n = 1 (0, 1, 2, …, 9)
• unique_digits = 9 # number of unique digits available for the first digit (1 to 9)
• available_digits = 9 # number of available digits for the remaining digits (0 to 9 except the first digit)
• i = 2
  • unique_digits = 9 * 9 = 81
  • count += unique_digits = 91
  • available_digits = 8
• return count = 91

Time Complexity: The time complexity of this algorithm is O(1) because we are only looping through a maximum of 10 values (i.e. n <= 10).

Space Complexity: The space complexity of this algorithm is O(1) because we are not using any extra space.

Let us now implement this algorithm in Python.

Code:

1