Numbers With Repeated Digits - Leetcode Solution

Problem Statement: Given a positive integer n, return the count of all numbers with unique digits, x, where 0 ≤ x < 10n.

Solution: The problem is asking us to find the count of all numbers with unique digits from 0 to 10^n-1. Let's solve this problem step by step.

First, we need to understand that if a number has repeated digits, then it is not a unique digit number. For example, 11, 22, 33, etc. are not unique digit numbers, whereas 12, 34, 45, etc. are unique digit numbers.

For n=1, we have only 10 unique digit numbers from 0 to 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

For n=2, we can build the unique digit numbers by appending a digit to the previous unique digit numbers. For example, if we have 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 as unique digit numbers of n=1, then we can build the unique digit numbers of n=2 by appending 0 to 9 in the front: 10, 20, 30, 40, 50, 60, 70, 80, and 90. Also, we can append any digit from 0 to 9 to the unique digit numbers of n=1 to form a new unique digit number. For example, we can append 1 to 0, 2 to 0, 3 to 0, and so on to form 11, 12, 13, and so on. Similarly, we can append each digit from 0 to 9 to each unique digit number of n=1 and get all unique digit numbers of n=2.

For n=3, we can apply the same logic as n=2 and form new unique digit numbers from the unique digit numbers of n=2. We can append any digit from 0 to 9 to the unique digit numbers of n=2 to get all possible unique digit numbers of n=3.

As we can see, the pattern is repetitive, and we can use recursion to solve this problem. We define a recursive function countNumbersWithUniqueDigitsHelper that takes an integer n and returns the count of all unique digit numbers from 0 to 10^n-1. We initialize the count as 1 because the number 0 is unique. Then, we create a loop from 1 to n and multiply the count with the number of ways to select i digits from 10 digits without repetition, which is 998*...*(11-i) for i digits.

Note that we have taken 9 in the first two places because we can not take 0. The second multiplication is between 9 and 8 because we have already taken one digit. Similarly, the last multiplication is between (11-i) and (10-i) because we have already taken i-1 digits, and we can not use those digits anymore. Finally, we return the count as the answer.

Here is the code for the solution:

class Solution { public: int countNumbersWithUniqueDigits(int n) { if (n==0) return 1; int count = 1; for (int i=1; i<=n; i++){ int ways = 9; for(int j=0; j<i-1; j++){ ways *= (9-j); } count += ways; } return count; } };

Time Complexity: As we are using one nested loop, the time complexity of this solution is O(n^2).

Space Complexity: We are using a constant amount of space, so the space complexity of the solution is O(1).

The solution is optimized and meets the requirements of the problem statement.

1