Leetcode 357. Count Numbers with Unique Digits

Problem Explanation:

In this problem, we're asked to count all numbers that contain unique digits within an inclusive range from 0 up to x < 10^n. By unique, we mean each digit within the number should not repeat. For example, '123' is a number with unique digits but '112' is not, the digit '1' is repeating.

To understand this better, let's take an example: n = 2. Our range starts from 0 and ends at 99 (because 10^n, here 10^2 is equal to 100 where 0 <= x < 100). If we calculate all the numbers within this range which have unique digits, we'll get the count as 91.

This is calculated as:

• For one-digit numbers, all digits (0-9) are unique, so there are 10 unique numbers.
• For two-digit numbers, there are: 9 choices (1 to 9) for the first digit 9 choices (including 0 but excluding the first chosen digit) for the second digit So, in total, we have 9*9 = 81 two-digit unique numbers.
• Adding one and two digits unique numbers: 10 + 81 = 91

Solution Explanation:

The solution uses a formulaic approach based on the observation made above. The algorithm initially specifies the number of single-digit numbers (0-9) as uniqueDigits which are obviously unique and adds it to 'ans'. It then starts from 2-digit numbers and keeps on computing the number of n-digit unique number -> the first digit can be chosen from 1 to 9 (9 choices) and the second digit can be chosen from 0 to 9 excluding the first digit (9 more choices). This is done in a loop which goes up to n, and for each iteration, the availableNum (available choices) decreases by 1 and uniqueDigits keep on getting computed for each n. These are subsequently added into ans.

This solution doesn't use any additional space and only requires a few variables to keep track of the computation which keeps the space complexity to O(1). The time complexity will be O(n) as we are going through an iteration up to n.

Now let's dive into the code examples.

Python Solution

1
2python
3class Solution:
4    def countNumbersWithUniqueDigits(self, n: int) -> int:
5        if n==0:
6            return 1
7        # There are 10 single digit numbers 
8        ans, uniqueDigits = 10, 9
9        for availableNum in range(9, 9-n+1, -1):
10            # Calculate the unique digits for that n and add it to ans 
11            uniqueDigits *= availableNum
12            ans += uniqueDigits
13        return ans

Java Solution

1
2java
3class Solution {
4    public int countNumbersWithUniqueDigits(int n) {
5        if(n==0)
6            return 1;
7        int ans = 10, uniqueDigits = 9;
8        for(int availableNum=9; n>1 && availableNum>0; --n, --availableNum){
9            uniqueDigits *= availableNum;
10            ans += uniqueDigits;
11        }
12        return ans;
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4    countNumbersWithUniqueDigits(n) {
5        if(n===0)
6            return 1;
7        let ans = 10, uniqueDigits = 9;
8        for(let availableNum=9; n>1 && availableNum>0; --n, --availableNum){
9            uniqueDigits *= availableNum;
10            ans += uniqueDigits;
11        }
12        return ans;
13    }
14}

C++ Solution

1
2c++
3class Solution {
4public:
5    int countNumbersWithUniqueDigits(int n) {
6        if(n==0)
7            return 1;
8        int ans = 10, uniqueDigits = 9;
9        for(int availableNum=9; n>1 && availableNum>0; --n, --availableNum){
10            uniqueDigits *= availableNum;
11            ans += uniqueDigits;;
12        }
13        return ans;
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int CountNumbersWithUniqueDigits(int n) {
5        if(n == 0)
6            return 1;
7        int ans = 10, uniqueDigits = 9;
8        for(int availableNum=9; n>1 && availableNum>0; --n, --availableNum){
9            uniqueDigits *= availableNum;
10            ans += uniqueDigits;
11        }
12        return ans;
13    }
14}

In each solution, we create a function that takes in an integer n (0 <= n <= 8). The countNumbersWithUniqueDigits function starts by checking if n is zero. If it is, it returns 1 as there is only one number (0) with unique digits in this range. If n is not zero, it calculates the number of unique digit numbers that can be formed in the range from 0 to 10^n, as explained earlier.## C.Lisp

1
2lisp
3
4(defmethod CountNumbersWithUniqueDigits ((n number))
5  (if (zerop n) 
6      1
7      (multiple-value-bind (ans uniqueDigits) (values 10 9)
8        (setf availableDigits 9)
9        (loop repeat (1- n) while (plusp availableDigits)
10                    do (progn (setf uniqueDigits (* uniqueDigits availableDigits))
11                              (setf ans (+ ans uniqueDigits))
12                              (setf availableDigits (1- availableDigits)))))
13        ans))

Conclusion:

These examples provide a solution for counting numbers with unique digits in the range from 0 to 10^n, for multiple programming languages including Python, Java, JavaScript, C++, C#, and Lisp.

They each use the same logic where single-digit numbers are counted first (0-9), then the count for two or more digit numbers is added by evaluating the possible choices for each digit. The first digit gets choices from 1-9, while subsequent ones have one less choice. This uses minimal space, with complexity O(1), and has reasonable time efficiency (O(n)) as it iterates up to n.

Hence, the problem of counting all numbers that have unique digits within an inclusive range can be solved effectively using the formulaic approach presented above in several programming languages.