# 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 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.

## 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 = {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;