Given a positive integer N, the task is to find the number of N-digit numbers such that at least one digit in the number has occurred more than once.
Examples:
Input: N = 2
Output: 9
Explanation:
All the 2-digit number such that at least 1 digits occurs more than once are {11, 22, 33, 44, 55, 66, 77, 88, 99}. Therefore, the total count is 9.Input: N = 5
Output: 62784
Naive Approach: The simplest approach to solve the given problem is to generate all possible N-digit numbers and count those numbers having at least one digit occurring more than once. After checking for all the numbers, print the value of the count as the resultant total count of numbers.
Algorithm
- Take input integer N from the user.
- Initialize a variable count to 0.
- Loop through all possible N-digit numbers, from 10^(N-1) to 10^N – 1.
- For each number, convert it to a string and check if any digit occurs more than once using a nested loop.
- If a digit occurs more than once, increment the count.
- After checking all numbers, print the value of the count as the resultant total count of numbers.
C++
#include <iostream>#include <string>#include <algorithm>#include <cmath>using namespace std;int main() { int N = 2; // set the value of N int countRepeated = 0; // initialize a counter variable // iterate through all N-digit numbers for (int i = pow(10, N - 1); i < pow(10, N); i++) { // convert the current number to a string string digits = to_string(i); // iterate through each digit in the string for (char digit : digits) { // count the number of occurrences of the current digit in the string if (count(digits.begin(), digits.end(), digit) > 1) { // if the digit appears more than once, increment the counter and move on to the next number countRepeated++; break; } } } // output the total count of N-digit numbers with at least one digit repeated cout << "Total count of N-digit numbers with at least one digit repeated: " << countRepeated << endl; return 0; // indicate successful program termination} |
Java
public class Main { public static void main(String[] args) { int N = 2; int countRepeated = 0; // Iterate through all N-digit numbers for (int i = (int) Math.pow(10, N - 1); i < Math.pow(10, N); i++) { // Convert the current number to a string String digits = String.valueOf(i); // Create an array to keep track of the occurrences of each digit int[] digitCount = new int[10]; // Iterate through each digit in the string for (char digit : digits.toCharArray()) { int numericDigit = Character.getNumericValue(digit); // Increment the count for the current digit digitCount[numericDigit]++; // If the digit appears more than once, increment the counter and move on to the next number if (digitCount[numericDigit] > 1) { countRepeated++; break; } } } System.out.println("Total count of N-digit numbers with at least one digit repeated: " + countRepeated); }} |
Python3
countRepeated = 0 # initialize a counter variableN = 2 # set the value of N# iterate through all N-digit numbersfor i in range(10**(N-1), 10**N): # convert the current number to a string digits = str(i) # iterate through each digit in the string for digit in digits: # count the number of occurrences of the current digit in the string if digits.count(digit) > 1: # if the digit appears more than once, increment the counter and move on to the next number countRepeated += 1 break# output the total count of N-digit numbers with at least one digit repeatedprint("Total count of N-digit numbers with at least one digit repeated: ", countRepeated) |
C#
using System;class Program { static void Main() { int N = 2; // Set the value of N int countRepeated = 0; // Initialize a counter variable // Iterate through all N-digit numbers for (int i = (int)Math.Pow(10, N - 1); i < Math.Pow(10, N); i++) { // Convert the current number to a string string digits = i.ToString(); // Create a boolean flag to check if a digit is // repeated bool digitRepeated = false; // Iterate through each digit in the string foreach(char digit in digits) { // Count the number of occurrences of the // current digit in the string int digitCount = digits.Split(digit).Length - 1; // If the digit appears more than once, set // the flag and break out of the loop if (digitCount > 1) { digitRepeated = true; break; } } // If at least one digit is repeated, increment // the counter if (digitRepeated) { countRepeated++; } } // Output the total count of N-digit numbers with at // least one digit repeated Console.WriteLine( "Total count of N-digit numbers with at least one digit repeated: " + countRepeated); }} |
Javascript
function countNumbersWithRepeatedDigit(N) { let countRepeated = 0; // Iterate through all N-digit numbers for (let i = Math.pow(10, N - 1); i < Math.pow(10, N); i++) { // Convert the current number to a string const digits = i.toString(); // Create a boolean flag to check if a digit is repeated let digitRepeated = false; // Iterate through each digit in the string for (let j = 0; j < digits.length; j++) { // Count the number of occurrences of the current digit in the string const digitCount = digits.split(digits[j]).length - 1; // If the digit appears more than once, set the flag and break out of the loop if (digitCount > 1) { digitRepeated = true; break; } } // If at least one digit is repeated, increment the counter if (digitRepeated) { countRepeated++; } } // Output the total count of N-digit numbers with at least one digit repeated console.log( "Total count of N-digit numbers with at least one digit repeated: " + countRepeated );}const N = 2; // Set the value of NcountNumbersWithRepeatedDigit(N); |
Output
Total count of N-digit numbers with at least one digit repeated: 9
Time Complexity: O(N *10N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because the above problem has Overlapping subproblems and an Optimal substructure. The subproblems can be stored in dp[][][] table memoization where dp[digit][mask][repeated] stores the answer from the digitth position till the end, where the mask stores all the digits included in the number till now and repeated denotes if any digit has occurred more than once. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[50][1024][2] with all values as -1 that stores the result of each recursive call.
- Define a recursive function, say countOfNumbers(digit, mask, repeated, N) by performing the following steps.
- If the value of a digit is equal to (N + 1) then return 1 as a valid N-digit number is formed if repeated is equal to true. Otherwise, return 0.
- If repeated is equal to true, then return pow(10, N – digit + 1).
- If the result of the state dp[digit][mask][repeated] is already computed, return this value dp[digit][mask][repeated].
- If the current digit is 1, then any digit from [1, 9] can be placed and if N = 1, then 0 can be placed as well.
- Iterate over the range [N == 1 ? 0 : 1, 9] using the variable i and perform the following steps:
- If the ith bit of the mask is set, then add the value of countOfNumbers(digit + 1, mask|(1<<i), 1, N).
- Otherwise, add the value of countOfNumbers(digit + 1, mask|(1<<i), 0, N).
- Otherwise, iterate over the range [0, 9] using the variable i and perform the following steps:
- If the ith bit of the mask is set, then add the value of countOfNumbers(digit + 1, mask|(1<<i), 1, N).
- Otherwise, add the value of countOfNumbers(digit + 1, mask|(1<<i), 0, N).
- Return the sum of all possible valid placements of digits val as the result from the current recursive call.
- Print the value returned by the function countOfNumbers(1, 0, 0, N) as the resultant count of N-digit number satisfying the given criteria.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int dp[50][1 << 10][2];// Function to find the number of N// digit numbers such that at least// one digit occurs more than onceint countOfNumbers(int digit, int mask, bool repeated, int n){ // Base Case if (digit == n + 1) { if (repeated == true) { return 1; } return 0; } // If repeated is true, then for // remaining positions any digit // can be placed if (repeated == true) { return pow(10, n - digit + 1); } // If the current state has already // been computed, then return it int& val = dp[digit][mask][repeated]; if (val != -1) { return val; } // Stores the count of number for // the current recursive calls val = 0; // If current position is 1, then // any digit can be placed. // If n = 1, 0 can be also placed if (digit == 1) { for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if (mask & (1 << i)) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } // Otherwise else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // For remaining positions any // digit can be placed else { for (int i = 0; i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if (mask & (1 << i)) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // Return the resultant count for // the current recursive call return val;}// Function to count all the N-digit// numbers having at least one digit's// occurrence more than oncevoid countNDigitNumber(int N){ // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Function to count all possible // number satisfying the given // criteria cout << countOfNumbers(1, 0, 0, N);}// Driver Codeint main(){ int N = 2; countNDigitNumber(N); return 0;} |
Java
import java.util.Arrays;// Java program for the above approachclass GFG { public static int[][][] dp = new int[50][1 << 10][2]; // Function to find the number of N // digit numbers such that at least // one digit occurs more than once public static int countOfNumbers(int digit, int mask, int repeated, int n) { // Base Case if (digit == n + 1) { if (repeated == 1) { return 1; } return 0; } // If repeated is true, then for // remaining positions any digit // can be placed if (repeated == 1) { return (int) Math.pow(10, n - digit + 1); } // If the current state has already // been computed, then return it int val = dp[digit][mask][repeated]; if (val != -1) { return val; } // Stores the count of number for // the current recursive calls val = 0; // If current position is 1, then // any digit can be placed. // If n = 1, 0 can be also placed if (digit == 1) { for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if ((mask & (1 << i)) > 0) { val += countOfNumbers(digit + 1, mask | (1 << i), 1, n); } // Otherwise else { val += countOfNumbers(digit + 1, mask | (1 << i), 0, n); } } } // For remaining positions any // digit can be placed else { for (int i = 0; i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if ((mask & (1 << i)) > 0) { val += countOfNumbers(digit + 1, mask | (1 << i), 1, n); } else { val += countOfNumbers(digit + 1, mask | (1 << i), 0, n); } } } // Return the resultant count for // the current recursive call return val; } // Function to count all the N-digit // numbers having at least one digit's // occurrence more than once public static void countNDigitNumber(int N) { // Initialize dp array with -1 for (int i = 0; i < 50; i++) { for (int j = 0; j < 1 << 10; j++) { for (int k = 0; k < 2; k++) { dp[i][j][k] = -1; } } } // Function to count all possible // number satisfying the given // criteria System.out.println(countOfNumbers(1, 0, 0, N)); } // Driver Code public static void main(String args[]) { int N = 2; countNDigitNumber(N); }}// This code is contributed by gfgking. |
Python3
# Python program for the above approachdp = [[[-1 for i in range(2)] for i in range(1 << 10)] for i in range(50)]# Function to find the number of N# digit numbers such that at least# one digit occurs more than oncedef countOfNumbers(digit, mask, repeated, n): global dp # Base Case if (digit == n + 1): if (repeated == True): return 1 return 0 # If repeated is true, then for # remaining positions any digit # can be placed if (repeated == True): return pow(10, n - digit + 1) # If the current state has already # been computed, then return it val = dp[digit][mask][repeated] if (val != -1): return val # Stores the count of number for # the current recursive calls val = 4 # If current position is 1, then # any digit can be placed. # If n = 1, 0 can be also placed if (digit == 1): for i in range((0 if (n==1) else 1),10): # If a digit has occurred # for the second time, then # set repeated to 1 if (mask & (1 << i)): val += countOfNumbers(digit + 1, mask | (1 << i), 1, n) # Otherwise else: val += countOfNumbers(digit + 1, mask | (1 << i), 0, n) # For remaining positions any # digit can be placed else: for i in range(10): # If a digit has occurred # for the second time, then # set repeated to 1 if (mask & (1 << i)): val += countOfNumbers(digit + 1, mask | (1 << i), 1, n) else: val += countOfNumbers(digit + 1, mask | (1 << i), 0, n) # Return the resultant count for # the current recursive call dp[digit][mask][repeated] = val return dp[digit][mask][repeated]# Function to count all the N-digit# numbers having at least one digit's# occurrence more than oncedef countNDigitNumber(N): # Function to count all possible # number satisfying the given # criteria print (countOfNumbers(1, 0, 0, N))# Driver Codeif __name__ == '__main__': N = 2 countNDigitNumber(N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{public static int[,,] dp = new int[50, 1 << 10, 2];// Function to find the number of N// digit numbers such that at least// one digit occurs more than oncepublic static int countOfNumbers(int digit, int mask, int repeated, int n){ // Base Case if (digit == n + 1) { if (repeated == 1) { return 1; } return 0; } // If repeated is true, then for // remaining positions any digit // can be placed if (repeated == 1) { return(int)Math.Pow(10, n - digit + 1); } // If the current state has already // been computed, then return it int val = dp[digit, mask, repeated]; if (val != -1) { return val; } // Stores the count of number for // the current recursive calls val = 0; // If current position is 1, then // any digit can be placed. // If n = 1, 0 can be also placed if (digit == 1) { for(int i = (n == 1 ? 0 : 1); i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if ((mask & (1 << i)) > 0) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } // Otherwise else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // For remaining positions any // digit can be placed else { for(int i = 0; i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if ((mask & (1 << i)) > 0) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // Return the resultant count for // the current recursive call return val;}// Function to count all the N-digit// numbers having at least one digit's// occurrence more than oncepublic static void countNDigitNumber(int N){ // Initialize dp array with -1 for(int i = 0; i < 50; i++) { for(int j = 0; j < 1 << 10; j++) { for(int k = 0; k < 2; k++) { dp[i, j, k] = -1; } } } // Function to count all possible // number satisfying the given // criteria Console.Write(countOfNumbers(1, 0, 0, N));}// Driver Codepublic static void Main(){ int N = 2; countNDigitNumber(N);}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program for the above approachlet dp = new Array(50).fill(0) .map(() => new Array(1 << 10).fill(0) .map(() => new Array(2).fill(-1)));// Function to find the number of N// digit numbers such that at least// one digit occurs more than oncefunction countOfNumbers(digit, mask, repeated, n) { // Base Case if (digit == n + 1) { if (repeated == true) { return 1; } return 0; } // If repeated is true, then for // remaining positions any digit // can be placed if (repeated == true) { return Math.pow(10, n - digit + 1); } // If the current state has already // been computed, then return it let val = dp[digit][mask][repeated]; if (val != -1) { return val; } // Stores the count of number for // the current recursive calls val = 0; // If current position is 1, then // any digit can be placed. // If n = 1, 0 can be also placed if (digit == 1) { for (let i = (n == 1 ? 0 : 1); i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if (mask & (1 << i)) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } // Otherwise else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // For remaining positions any // digit can be placed else { for (let i = 0; i <= 9; ++i) { // If a digit has occurred // for the second time, then // set repeated to 1 if (mask & (1 << i)) { val += countOfNumbers( digit + 1, mask | (1 << i), 1, n); } else { val += countOfNumbers( digit + 1, mask | (1 << i), 0, n); } } } // Return the resultant count for // the current recursive call return val;}// Function to count all the N-digit// numbers having at least one digit's// occurrence more than oncefunction countNDigitNumber(N) { // Initialize dp array with -1 // Function to count all possible // number satisfying the given // criteria document.write(countOfNumbers(1, 0, 0, N));}// Driver Codelet N = 2;countNDigitNumber(N);</script> |
Output
9
Time Complexity: O(10 * N * 210 * 2 )
Auxiliary Space: O(N * 210 * 2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
