Numbers with Repeated Digits

Approach 1

We will discuss a straightforward approach to solve this problem. Consider all the numbers between 1 and ‘N’ and look for a repeated digit in each one of them. Increase the count if a number satisfies the criteria.

Algorithm

1. Run a loop from 1 to N and let the current element be ‘X’.
   1. Extract the digits in ‘X’.
   2. Create a frequency vector of size 10 to count the number of digits from 0 to 9 in ‘X’.
   3. Check if any of the digits has frequency greater than 1.
   4. If yes, increase the answer by 1.
2. Output the answer.

Program

#include <iostream>
#include <vector>
using namespace std;

// Function to count the numbers with at least one repeated digit.
int findValidNums(int n)
{
   // Variable to store the numbers with no repeated digit.
   int validCnt = 0;

   for (int i = 1; i <= n; i++)
   {
       // Vector to maintain the frequency of digits in the current value of i.
       vector<int> digitsCnt(10);

       int val = i;

       // To check if the current value has no repeated digit.
       bool isRepeatedDigit = false;

       while (val)
       {
           // Current digit.
           digitsCnt[val % 10]++;

           // If we have encountered this digit before.
           // If it is true, it implies the value contains repeated digit, hence break.
           if (digitsCnt[val % 10] > 1)
           {
               isRepeatedDigit = true;
               break;
           }

           val = val / 10;
       }

       // Add the current value if it contains no repeated digit.
       if (!isRepeatedDigit)
           validCnt++;
   }

   // Return the count of numbers with at least one repeated digit.
   return n - validCnt;
}

int main()
{
   // Take input.
   int n;
   cin >> n;

   // Find the count and print it.
   int countValidNums = findValidNums(n);
   cout << countValidNums << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

100

Output

10

Time Complexity

The time complexity of the above approach is O(N * logN), where ‘N’ is the input parameter.
It is because we are running a loop till ‘N’ and for each element we are doing logN operations to get all the digits.

Space Complexity

The space complexity of the above approach is O(1).
It is because we are using constant space to execute the algorithm.

Approach 2

The count of numbers with at least one repeated digit in the range [1, ‘N’] is equivalent to ‘N - X’, where ‘X’ = Count of numbers with no repeated digit. Let us focus on counting the numbers with no repeated digit in the range [1, ‘N’] as this is more convenient.

Now let us ask a simple question - How many d-digit numbers are there with no repeated digit? This is a simple Permutation and Combination question. Let us understand with an example.

Let d = 5.

Here we can fill P1 with any value from the set {1, 2, 3, 4, 5, 6, 7, 8, 9}.

P2 can be filled with any number which belongs to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} - {P1}.

P3 can be filled with any number which belongs to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} - {P1, P2}.

P4 can be filled with any number which belongs to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} - {P1, P2, P3}.

P5 can be filled with any number which belongs to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} - {P1, P2, P3, P4}.

You can calculate the size of the sets mentioned above. Using the size of the sets the required count of 5-digit numbers = 9 * 9 * 8 * 7 * 6.

We can generalise this to d-digit numbers as follows:

Count_d = 9 * 9 * 8 * 7 * 6 … * (10 - (d - 1)) = 9 * 9! / (10 - d)!

Let’s come back to the original question. Let the number of digits in the input parameter be ‘D’. Then we can find the count of the required number with fewer digits than ‘D’ using the above formula. For the numbers with ‘D’ digits, we need to ensure that the number included in the count is less than ‘N + 1’.

Algorithm

1. Take the input number ‘N’.
2. Count the number of digits in ‘N’ and let it be ‘D’.
3. Create a function countNums(X) with input parameter ‘X’ that returns the count of ‘X’-digit numbers with no repeated digit using the formula described above.
4. Assign ‘COUNT_VALID_NUM’ = 0. This will store the count of numbers in [1, ‘N’] with no repeated digit.
5. Consider all numbers with less than ‘D’ digits. 
6. Run a for loop with variable ‘X’ from 1 to ‘D - 1’ and do the following:
   1. Add the count of valid ‘X’-digit numbers to ‘COUNT_VALID_NUM’ using the function countNums(X) declared above.
7. For the ‘D’-digit numbers, extract the digits of ‘N’ and store them in a vector ‘DIGITS’.
8. Include only those ‘D’-digit numbers which are less than ‘N’. More details about how to do this is well-presented in the code with comments.

Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the number of digits.
int findNumDigits(int v)
{
   if (v == 0)
       return 1;
   int num = 0;

   // Standard technique to find the count of digits.
   while (v > 0)
   {
       num++;
       v = v / 10;
   }

   // Return the count.
   return num;
}

// Function to calculate the factorial of a number.
int factorialCalc(int i)
{
   if (i <= 1)
       return i;
   return i * factorialCalc(i - 1);
}

// Function to calculate the formula described in the approach.
int countNums(int d)
{
   // Formula derivation is described in the approach.
   return 9 * factorialCalc(9) / factorialCalc(10 - d);
}

// Function to find out how many digits upto d (exclusive) are used in a number before.
int usableDigits(vector<int> &fre, int d)
{
   int usableDig = 0;
   for (int i = 0; i < d; i++)
   {
       if (fre[i] == 0)
           usableDig++;
   }
   return usableDig;
}

// Function to count the numbers with at least one repeated digit.
int findValidNums(int n)
{
   // Variable to store the numbers with no repeated digit.
   int validCnt = 0;

   // Count the digits.
   int numDigits = findNumDigits(n);

   // Calculate the count of numbers with no repeated digit having less than 'NUM_DIGITS' digits.
   for (int i = 1; i < numDigits; i++)
   {
       validCnt += countNums(i);
   }

   // Vector to store the digits in 'N'.
   vector<int> digits;

   // Standard technique to find the digits.
   int val = n;
   while (val > 0)
   {
       digits.push_back(val % 10);
       val = val / 10;
   }
   reverse(digits.begin(), digits.end());

   // To count the numbers having 'NUM_DIGITS' digits less than 'N' with no repeated digit.
   // If we fill the first position with a decimal value less than digits[0], we can fill the rest positions with any value as long as they are unique.
   // The number of ways to fill the remaining positions can be calculated in the same way we did in the approach.
   // The formula used here resembles the countNums function.
   validCnt += (digits[0] - 1) * factorialCalc(9) / factorialCalc(10 - numDigits);

   // For utility purpose.
   int lim = 0;

   // To keep track of digits used so far.
   vector<int> used(10);

   // First digit is already used.
   used[digits[0]] = 1;

   // Fill the remaining positions so that the generated number has no repeated digit.
   for (int i = 1; i < numDigits; i++)
   {
       if (i == numDigits - 1)
           lim = 1;

       // We can fill the current position with only those digits which are not used so far.
       // This value is given by usableDigits function.
       // Till now 10 - (i + 1) digits have been used.
       // Formula used here and the above explanation can be used to generate the count of required numbers in a similar fashion described in the approach.
       validCnt += usableDigits(used, digits[i] + lim) * factorialCalc(10 - (i + 1)) / factorialCalc(10 - numDigits);

       // If current digit is already used, we cannot any more numbers.
       if (used[digits[i]])
           break;
      
       // Mark the current digit as used.
       used[digits[i]] = 1;
   }

   // Return the count of numbers with at least one repeated digit.
   return n - validCnt;
}

int main()
{
   // Take input.
   int n;
   cin >> n;

   // Find the count and print it.
   int countValidNums = findValidNums(n);
   cout << countValidNums << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

100

Output

10

Time Complexity

The time complexity of the above approach is O((logN) ^ 2), where ‘N’ is the input parameter.
It is because we are finding the number of digits in the input parameter ‘N’ which is an O(logN) operation and for each digit we are calculating the factorial function with O(logN) time complexity.

Space Complexity

The space complexity of the above approach is O(1).
It is because we are using constant space to execute the algorithm.

Key Takeaways

In this blog, we learned about an interesting problem, namely numbers with repeated digits. We solved the problem efficiently using the insight from a PERMUTATION and COMBINATION problem. We discussed the brute approach and efficient approach and appreciated the difference in the time complexity.

Check out this problem - Find Duplicate In Array

Hence learning never stops, and there is a lot more to learn.
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!