## Approach 1

The naive approach to solve this problem is to iterate through all the numbers of N-digits for which at least one digit repeats and for each number, keep a count of the frequency of all the digits in it and if the frequency of any digit is more than one, then increment the count by 1.

And the obtained count is our required result.

### Algorithm

- Initialize the ‘COUNT’ to 0.
- Traverse all N-digit numbers starting from 10 ^ (N - 1) to 10 ^ (N) - 1.

In each iteration, store the frequency of each digit of the number and check if the frequency exceeds 1, increment ‘COUNT’ by 1.

- Return ‘COUNT’.

### Program

```
#include <iostream>
#include<cmath>
using namespace std;
// Function to calculate the count of N-digit numbers having at least one digit repeating.
int totalCount(int n)
{
// First N-digit number.
int start = ceil(pow(10, n - 1));
// Last N-digit number.
int end = ceil(pow(10, n)) - 1;
// Store count of N-digits no. with at least one digit repeating.
int count = 0;
for (int i = start; i <= end; i++)
{
int temp = i;
// Store the frequency of each digit.
int frequency[10] = {0};
while (temp)
{
// Calculate remainder after dividing with 10.
int rem = temp % 10;
frequency[rem]++;
temp /= 10;
}
for (int j = 0; j < 10; j++)
{
if (frequency[j] >= 2)
{
count++;
break;
}
}
}
return count;
}
int main()
{
// Input No. of digits.
int n;
cin >> n;
cout << totalCount(n);
return 0;
}
```

### Input

`5`

### Output

`62784`

### Time Complexity

**O(N * (10 ^ N)), **where ‘N’ is the given number.

Because the count of all N-digit numbers are in order of ‘10^N’ and traversing each number takes O(N).

### Space Complexity

**O(1).**

As we didn’t use extra space except for a few variables.

## Approach 2

In this approach, we will discuss how we can find the count of N-digit numbers having at least one repeated digit solution using dynamic programming.

All the subproblems are stored in 3-dimensional array, i.e., DP[][][]. Here, DP[D][M][R] stores the count of all D-digit numbers with at least one digit repeated from digit-’D’ position to end, ‘M’ stores all digits included in the number till now, and ‘R’ denotes whether the digit occurs more than once. Here, we recursively call the function and memoize the result.

### Algorithm

- Create a global 3-dimensional array DP[50][1024][2] and initialize it to -1. It is used to memoize the result. DP[D][M][R] stores the answer from D-th position till the end, where ‘M’ is all the digits included till now and ‘R’ denotes whether any digit is repeated or not.
- Create a function named ‘recursiveFunction()’ which takes four arguments ‘D’, ‘M’, ‘R’, and ‘N’ where ‘N’ is the given number. Then perform the following steps:

- If the value of ‘D’ is equal to ‘N + 1’ and ‘R’ is true then return 1, otherwise, return 0. This is the base condition to terminate the recursive call.
- If ‘R’ is true then return power(10, N - D + 1).
- If dp[D][M][R] is not equal to -1, return dp[D][M][R]. This means that the value is already computed.
- If N == 1, then all 10 digits [0,9] can be placed but if N > 1, then only [1,9] can be placed in the first position.
- Iterate all the digit from [0,9] and check if ith bit is already set then add recursiveFunction(D+1,M|(1<<i),1,N) otherwise add recursiveFunction(D+1, M | (1<<i), 0,N) to DP[D][M][R].

- Call recursiveFunction(N,1,0,0) for answer.

### Program

```
#include <iostream>
#include <cmath>
using namespace std;
// Initialize global multidimensional dp array.
int dp[50][2024][2];
// Function to calculate the count of all N-digit numbers with at least one digit repeated.
int recursiveFunction(int num, int d, int m,
bool r)
{
// Base condition to terminate the recursive function.
if (d == num + 1)
{
if (not r)
return 0;
return 1;
}
// if the number is repeated.
if (r)
return pow(10, num - d + 1);
// if dp[d][m][r] is already computed.
if (dp[d][m][r] != -1)
{
return dp[d][m][r];
}
dp[d][m][r] = 0;
// only for 1 digit
if (d == 1)
{
int i;
if (num == 1)
i = 0;
else
i = 1;
for (i; i < 10; i++)
{
if (m & (1 << i))
{
dp[d][m][r] += recursiveFunction(num, d + 1, m | (1 << i), 1);
}
else
{
dp[d][m][r] += recursiveFunction(num, d + 1, m | (1 << i), 0);
}
}
}
else
{
for (int i = 0; i < 10; i++)
{
if (m & (1 << i))
{
dp[d][m][r] += recursiveFunction(num, d + 1, m | (1 << i), 1);
}
else
{
dp[d][m][r] += recursiveFunction(num, d + 1, m | (1 << i), 0);
}
}
}
return dp[d][m][r];
}
int main()
{
// input number of digits.
int n;
cin >> n;
// initialize all values of dp to -1;
memset(dp, -1, sizeof(dp));
cout << recursiveFunction(n, 1, 0, 0);
return 0;
}
```

### Input

`4`

### Output

`4455`

### Time Complexity

**O(10 * N * (2^10) * 2)**, where ‘N’ is the given number.

Because we traverse dp array of size N * 1024 * 2.

### Space Complexity

**O(N * (2^10) * 2)**, where ‘N’ is the given number.

As we are creating a ‘DP’ array of size N * 1024 * 2.

## Approach 3

In this approach, we will discuss how to find the count of N-digit numbers having at least one repeated digit solution using combinatorics. With the help of combinatorics, we will first calculate all the possible N-digit numbers in which all digits are distinct. Then, the count of all N-digit numbers with at least one digit repeating is equal to the number of all possible N-digits numbers minus all the possible N-digit numbers in which all digits are distinct.

While we try to calculate all the possible N-digit numbers in which all digits are distinct, we encounter two conditions:

- If N > 10, then the count will be 0 as we have only 0,1,2,3,4,5,6,7,8,9 available digits. Hence, if N is greater than 10, surely at least one digit is repeated.
- If N <= 10, then count will be (10-1)*(10-1)!/(10-N)! . This formula is derived by the fact that 1st digit is always non-zero and for the rest of the digit, we can take any digit except the previously taken digit because suppose we have taken 1st digit as zero and the number formed is 09 then this is not a two-digit number as leading zeros cannot be counted in any number.

### Algorithm

There are two broad cases to consider:

- If N>10: the count will equal all possible N-digit numbers.
- Else: Calculate total count of numbers with all digits distinct using formula (10-1)*(10-1)!/(10-N)!.

Also, calculate total possible N-digit numbers. Our final count will be equal to the difference of both results.

### Program

```
#include <iostream>
#include <cmath>
using namespace std;
// Function to calculate the count of all N-digit numbers with at least one digit repeating.
int totalDigit(int n)
{
if (n > 10)
{
// Calculate all numbers upto N-digits.
int a = pow(10, n);
// Calculate all numbers upto (N-1)-digits.
int b = pow(10, n - 1);
int count = a - b;
return a - b;
}
else
{
// Total no. of N-digits numbers.
int a = ceil(pow(10, n)) - ceil(pow(10, n - 1));
int nonrepeating = 9;
for (int i = 10 - n + 1; i < 10; i++)
{
nonrepeating *= i;
}
int count = a - nonrepeating;
return count;
}
}
int main()
{
// Input no. of digits.
int n;
cin >> n;
cout << totalDigit(n);
return 0;
}
```

### Input

`2`

### Output

`9`

### Time Complexity

**O(N)**, where ‘N’ is the given number.

Because we calculate all combinations of N.

### Space Complexity

**O(1)**, as we didn’t use any extra space.

## Key Takeaways

In this blog, we have learned three approaches to solve the problem: count all N-digits numbers with at least one digit repeating. The first approach is the brute force approach. Brute forces are always the first to go. We also discussed how to optimize the first approach to reduce the time complexity by using Dynamic Programming. After that, we discuss the most efficient approach, i.e., Combinatorics.

Hence learning never stops, and there is a lot more to learn.

Check out this problem - __Frog Jump__

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!