# Solution For Numbers With Repeated Digits

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 9*9*8*…*(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.

## Step by Step Implementation For Numbers With Repeated Digits

class Solution { public int numDupDigitsAtMostN(int N) { if (N < 10) return 0; int res = 0, n = N + 1; // count the number of unique digits in N int count = 0, uniq = 0; for (int i = 0; i <= 9; i++) { if (((N >> i) & 1) == 1) { count++; uniq |= (1 << i); } } // count the number of unique digits in N - 1 for (int i = 0; i <= 9; i++) { if (((N - 1 >> i) & 1) == 1) { count--; uniq &= ~(1 << i); } } // case 1: N has same digits as N - 1 if (count == 0) return 0; // case 2: N has unique digits if (uniq == (1 << count) - 1) return count * (count - 1) / 2; // case 3: N has repeated digits res += count * (count - 1) / 2; int p = 1; // case 3.1: N has leading 0 while ((n / p) % 10 == 0) { res -= p; p *= 10; } // case 3.2: N has repeated digits while (p < n) { res += countUnique(n / p, uniq); uniq |= (1 << (n / p % 10)); count++; p *= 10; } return res; } // count the number of unique digits in n that is not in uniq private int countUnique(int n, int uniq) { int res = 0, p = 1; while (p <= n) { int d = n / p % 10; for (int i = 0; i < d; i++) { if ((uniq & (1 << i)) == 0) res += p; } if ((uniq & (1 << d)) != 0) break; res++; uniq |= (1 << d); p *= 10; } return res; } }

class Solution: def numsSameConsecDiff(self, N: int, K: int) -> List[int]: # base case: if N == 1: return [i for i in range(10)] # recursive case: else: # initialize list to store results results = [] # get list of numbers with repeated digits for N-1 prev = self.numsSameConsecDiff(N-1, K) # for each number in the list of N-1 numbers for num in prev: # get the last digit of the number lastDigit = num % 10 # add the number to the results list if its last digit plus K is between 0 and 9 (inclusive) if lastDigit + K < 10: results.append(num*10 + lastDigit + K) # add the number to the results list if its last digit minus K is between 0 and 9 (inclusive) and K != 0 if lastDigit - K >= 0 and K != 0: results.append(num*10 + lastDigit - K) return results

/** * @param {number} N * @return {number} */ var numDupDigitsAtMostN = function(N) { //edge case if(N < 10) return 0; let count = 0; // start at 10 because there are no duplicated digits at most 9 for(let i = 10; i <= N; i++){ let seen = {}; let isDup = false; // turn number into string so we can iterate through each digit let num = i.toString(); for(let j = 0; j < num.length; j++){ // if digit has been seen, set isDup to true and break out of loop if(seen[num[j]]){ isDup = true; break; // otherwise, add digit to seen object } else { seen[num[j]] = true; } } // if isDup is true, increment count if(isDup){ count++; } } return count; };

class Solution { public: int numDupDigitsAtMostN(int N) { // return the number of integers between 1 and N that have at least one repeated digit int count = 0; for (int i = 1; i <= N; i++) { bool seen[10] = {false}; int j = i; while (j > 0) { if (seen[j % 10]) { count++; break; } seen[j % 10] = true; j /= 10; } } return count; } };

using System; using System.Collections.Generic; public class Solution { public int NumDupDigitsAtMostN(int N) { int result = 0; // your code goes here return result; } }