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[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;
}
}