Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Constraints
3.
Approach 1
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Approach 2
4.1.
Algorithm
4.2.
 Program
4.3.
Input
4.4.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Approach 3
5.1.
Algorithm
5.2.
Program
5.3.
Input
5.4.
Output
5.5.
Time Complexity
5.6.
Space Complexity
6.
Key Takeaways
Last Updated: Mar 27, 2024

How to find all N digit numbers with at least one repeated digit

Author Ujjawal Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In this blog, we are going to discuss a problem based on dynamic programming in which we are asked to find the count of all N-digit numbers with at least one digit repeating. Dynamic Programming based coding problems is widely asked in competitive programming contests and in various coding interviews. Here we will discuss three approaches. The first one will be brute force, then we will see a dynamic programming approach, and at the end, we will discuss Combinatorics based efficient approach.

The Problem Statement

Suppose you are given an integer ‘N’; your task is to find the count of all N-digits numbers having at least one digit repeated.

Example- For N = 2, we have 11, 22, 33, 44, 55, 66, 77, 88, 99 are the numbers with repeated digits. Hence the count will be 9 in this case.

Constraints

1 <= N <= 50.

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

  1. Initialize the ‘COUNT’ to 0.
  2. 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.

  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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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

  1. 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.
  2. 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].
  1. 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;
}
You can also try this code with Online C++ Compiler
Run Code

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: 

  1. 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.
  2. 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:

  1. If N>10: the count will equal all possible N-digit numbers.
  2. 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;
}
You can also try this code with Online C++ Compiler
Run Code

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!

 

Live masterclass