Count of N-digit numbers having equal count of distinct odd and even digits
Given a positive integer N, the task is to count the number of N-digit numbers such that the count of distinct odd and distinct even digits in the number is the same.
Examples:
Input: N = 2
Output : 45
Explanation:
For a 2-digit number, in order to satisfy the condition, the first digit can be even and second digit odd, or the second digit can be odd and first digit even. For the first case there are (4 X 5) = 20 possibilities and for the second case there are (5 X 5) = 25 possibilities. Hence the answer is 45.Input: N = 3
Output: 135
Naive Approach: The simplest approach to solve the given problem is to generate all possible N-digit numbers and count those numbers where the number of distinct odd and even digits are the same. After checking for all the numbers, print the value of the count as the resultant total count of numbers.
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[index][evenMask][oddMask] stores the answer from the ith index position till the end, where evenMask is used to determine the number of distinct even digits in the number and oddMask is used to determine the number of distinct odd digits in the number using a bitmask. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[100][1<<5][1<<5] with all values as -1 that stores the result of each recursive call.
- Define a recursive function, say countOfNumbers(index, evenMask, oddMask, N) by performing the following steps
- If the value of an index is equal to (N + 1),
- Calculate the count of set bits in evenMask and oddMask.
- If they have the same count, then the number of distinct even and odd digits is the same, and hence return 1 as a valid N-digit number has been formed.
- Else return 0.
- If the result of the state dp[index][evenMask][oddMask] is already computed, return this value dp[index][evenMask][oddMask].
- If the current index is 1, then any digit from [1- 9] can be placed and if N = 1, then 0 can be placed as well.
- For all other indices, any digit from [0-9] can be placed.
- For any digit placed set the (digit / 2)th bit of the evenMask or oddMask to 1 depending on the parity of the digit. It denotes that the particular digit is present in the number. Since we are dividing the digit by 2, bitmask of size (1 << 5) is sufficient for each oddMask and evenMask.
- After making a valid placement, recursively call the countOfNumbers function for (index + 1).
- Return the sum of all possible valid placements of digits as the answer.
- If the value of an index is equal to (N + 1),
- After completing the above steps, print the value returned by the function countOfNumbers(1, 0, 0, N) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the dp-states int dp[100][1 << 5][1 << 5]; // Recursive Function to find number // of N-digit numbers which has equal // count of distinct odd & even digits int countOfNumbers( int index, int evenMask, int oddMask, int N) { // If index is N + 1 if (index == N + 1) { // Find the count of set bits // in the evenMask int countOfEvenDigits = __builtin_popcount(evenMask); // Find the count of set bits // in the oddMask int countOfOddDigits = __builtin_popcount(oddMask); // If the count of set bits in both // masks are equal then return 1 // as they have equal number of // distinct odd and even digits if (countOfOddDigits == countOfEvenDigits) { return 1; } return 0; } int & val = dp[index][evenMask][oddMask]; // If the state has already // been computed if (val != -1) return val; val = 0; // If current position is 1, then // any digit from [1-9] can be // placed // If N = 1, 0 can be also placed if (index == 1) { for ( int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If digit is odd if (digit & 1) { // Set the (digit/2)th bit // of the oddMask val += countOfNumbers( index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } // Set the (digit/2)th bit // of the number evenMask else { val += countOfNumbers( index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // For remaining positions, any // digit from [0-9] can be placed else { for ( int digit = 0; digit <= 9; ++digit) { // If digit is odd if (digit & 1) { // Set the (digit/2)th // bit of oddMask val += countOfNumbers( index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } else { // Set the (digit/2)th // bit of evenMask val += countOfNumbers( index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // Return the answer return val; } // Function to find number of N-digit // numbers which has equal count of // distinct odd and even digits void countNDigitNumber( int N) { // Initialize dp array with -1 memset (dp, -1, sizeof dp); // Function Call cout << countOfNumbers(1, 0, 0, N); } // Driver Code int main() { int N = 3; countNDigitNumber(N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Stores the dp-states static int [][][] dp = new int [ 100 ][ 1 << 5 ][ 1 << 5 ]; // Returns number of set bits in a number static int __builtin_popcount( int n) { int d, t = 0 ; while (n > 0 ) { d = n % 2 ; n = n / 2 ; if (d == 1 ) t++; } return t; } // Recursive Function to find number // of N-digit numbers which has equal // count of distinct odd & even digits static int countOfNumbers( int index, int evenMask, int oddMask, int N) { // If index is N + 1 if (index == N + 1 ) { // Find the count of set bits // in the evenMask int countOfEvenDigits = __builtin_popcount(evenMask); // Find the count of set bits // in the oddMask int countOfOddDigits = __builtin_popcount(oddMask); // If the count of set bits in both // masks are equal then return 1 // as they have equal number of // distinct odd and even digits if (countOfOddDigits == countOfEvenDigits) { return 1 ; } return 0 ; } int val = dp[index][evenMask][oddMask]; // If the state has already // been computed if (val != - 1 ) return val; val = 0 ; // If current position is 1, then // any digit from [1-9] can be // placed // If N = 1, 0 can be also placed if (index == 1 ) { for ( int digit = (N == 1 ? 0 : 1 ); digit <= 9 ; ++digit) { // If digit is odd if ((digit & 1 ) != 0 ) { // Set the (digit/2)th bit // of the oddMask val += countOfNumbers( index + 1 , evenMask, oddMask | ( 1 << (digit / 2 )), N); } // Set the (digit/2)th bit // of the number evenMask else { val += countOfNumbers( index + 1 , evenMask | ( 1 << (digit / 2 )), oddMask, N); } } } // For remaining positions, any // digit from [0-9] can be placed else { for ( int digit = 0 ; digit <= 9 ; ++digit) { // If digit is odd if ((digit & 1 ) != 0 ) { // Set the (digit/2)th // bit of oddMask val += countOfNumbers( index + 1 , evenMask, oddMask | ( 1 << (digit / 2 )), N); } else { // Set the (digit/2)th // bit of evenMask val += countOfNumbers( index + 1 , evenMask | ( 1 << (digit / 2 )), oddMask, N); } } } // Return the answer return val; } // Function to find number of N-digit // numbers which has equal count of // distinct odd and even digits static void countNDigitNumber( int N) { // Initialize dp array with -1 for ( int i = 0 ; i < 100 ; i++) { for ( int j = 0 ; j < ( 1 << 5 ); j++) { for ( int k = 0 ; k < ( 1 << 5 ); k++) { dp[i][j][k] = - 1 ; } } } // Function Call System.out.println(countOfNumbers( 1 , 0 , 0 , N)); } // Driver code public static void main(String[] args) { int N = 3 ; countNDigitNumber(N); } } // This code is contributed by sanjoy_62 |
Python3
# Python program for the above approach: ## Stores the dp-states dp = [] # Function to count set bits in an integer # in Python def __builtin_popcount(num): # convert given number into binary # output will be like bin(11)=0b1101 binary = bin (num) # now separate out all 1's from binary string # we need to skip starting two characters # of binary string i.e; 0b setBits = [ones for ones in binary[ 2 :] if ones = = '1' ] return len (setBits) ## Recursive Function to find number ## of N-digit numbers which has equal ## count of distinct odd & even digits def countOfNumbers(index, evenMask, oddMask, N): ## If index is N + 1 if (index = = N + 1 ): ## Find the count of set bits ## in the evenMask countOfEvenDigits = __builtin_popcount(evenMask); ## Find the count of set bits ## in the oddMask countOfOddDigits = __builtin_popcount(oddMask); ## If the count of set bits in both ## masks are equal then return 1 ## as they have equal number of ## distinct odd and even digits if (countOfOddDigits = = countOfEvenDigits): return 1 return 0 val = dp[index][evenMask][oddMask] ## If the state has already ## been computed if (val ! = - 1 ): return val val = 0 ## If current position is 1, then ## any digit from [1-9] can be ## placed ## If N = 1, 0 can be also placed if (index = = 1 ): st = 1 if (N = = 1 ): st = 0 for digit in range (st, 10 ): ## If digit is odd if (digit & 1 ) = = 1 : ## Set the (digit/2)th bit ## of the oddMask val + = countOfNumbers(index + 1 , evenMask, oddMask | ( 1 << (digit / / 2 )), N) ## Set the (digit/2)th bit ## of the number evenMask else : val + = countOfNumbers(index + 1 , evenMask | ( 1 << (digit / / 2 )), oddMask, N) ## For remaining positions, any ## digit from [0-9] can be placed else : for digit in range ( 10 ): ## If digit is odd if (digit & 1 ) = = 1 : ## Set the (digit/2)th ## bit of oddMask val + = countOfNumbers(index + 1 , evenMask, oddMask | ( 1 << (digit / / 2 )), N) else : ## Set the (digit/2)th ## bit of evenMask val + = countOfNumbers(index + 1 , evenMask | ( 1 << (digit / / 2 )), oddMask, N) dp[index][evenMask][oddMask] = val ## Return the answer return val ## Function to find number of N-digit ## numbers which has equal count of ## distinct odd and even digits def countNDigitNumber(N): ## Initialize dp array with -1 for i in range ( 0 , 100 ): dp.append([]) for j in range ( 0 , 1 << 5 ): dp[i].append([]) for k in range ( 0 , 1 << 5 ): dp[i][j].append( - 1 ) ## Function Call print (countOfNumbers( 1 , 0 , 0 , N)) ## Driver code if __name__ = = '__main__' : N = 3 countNDigitNumber(N) |
C#
// C# program for the above approach using System; class GFG{ // Stores the dp-states static int [,,] dp = new int [100, 1 << 5, 1 << 5]; // Returns number of set bits in a number static int __builtin_popcount( int n) { int d, t = 0; while (n > 0) { d = n % 2; n = n / 2; if (d == 1) t++; } return t; } // Recursive Function to find number // of N-digit numbers which has equal // count of distinct odd & even digits static int countOfNumbers( int index, int evenMask, int oddMask, int N) { // If index is N + 1 if (index == N + 1) { // Find the count of set bits // in the evenMask int countOfEvenDigits = __builtin_popcount(evenMask); // Find the count of set bits // in the oddMask int countOfOddDigits = __builtin_popcount(oddMask); // If the count of set bits in both // masks are equal then return 1 // as they have equal number of // distinct odd and even digits if (countOfOddDigits == countOfEvenDigits) { return 1; } return 0; } int val = dp[index, evenMask, oddMask]; // If the state has already // been computed if (val != -1) return val; val = 0; // If current position is 1, then // any digit from [1-9] can be // placed // If N = 1, 0 can be also placed if (index == 1) { for ( int digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If digit is odd if ((digit & 1) != 0) { // Set the (digit/2)th bit // of the oddMask val += countOfNumbers( index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } // Set the (digit/2)th bit // of the number evenMask else { val += countOfNumbers( index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // For remaining positions, any // digit from [0-9] can be placed else { for ( int digit = 0; digit <= 9; ++digit) { // If digit is odd if ((digit & 1) != 0) { // Set the (digit/2)th // bit of oddMask val += countOfNumbers( index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } else { // Set the (digit/2)th // bit of evenMask val += countOfNumbers( index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // Return the answer return val; } // Function to find number of N-digit // numbers which has equal count of // distinct odd and even digits static void countNDigitNumber( int N) { // Initialize dp array with -1 for ( int i = 0; i < 100; i++) { for ( int j = 0; j < (1 << 5); j++) { for ( int k = 0; k < (1 << 5); k++) { dp[i, j, k] = -1; } } } // Function Call Console.Write(countOfNumbers(1, 0, 0, N)); } // Driver Code public static void Main() { int N = 3; countNDigitNumber(N); } } // This code is contributed by target_2. |
Javascript
<script> // javascript program for the above approach // Stores the dp-states var dp = Array(100).fill().map(()=>Array(1 << 5).fill().map(()=>Array(1 << 5).fill(0))); // Returns number of set bits in a number function __builtin_popcount(n) { var d, t = 0; while (n > 0) { d = n % 2; n = parseInt(n / 2); if (d == 1) t++; } return t; } // Recursive Function to find number // of N-digit numbers which has equal // count of distinct odd & even digits function countOfNumbers(index , evenMask , oddMask , N) { // If index is N + 1 if (index == N + 1) { // Find the count of set bits // in the evenMask var countOfEvenDigits = __builtin_popcount(evenMask); // Find the count of set bits // in the oddMask var countOfOddDigits = __builtin_popcount(oddMask); // If the count of set bits in both // masks are equal then return 1 // as they have equal number of // distinct odd and even digits if (countOfOddDigits == countOfEvenDigits) { return 1; } return 0; } var val = dp[index][evenMask][oddMask]; // If the state has already // been computed if (val != -1) return val; val = 0; // If current position is 1, then // any digit from [1-9] can be // placed // If N = 1, 0 can be also placed if (index == 1) { for (digit = (N == 1 ? 0 : 1); digit <= 9; ++digit) { // If digit is odd if ((digit & 1) != 0) { // Set the (digit/2)th bit // of the oddMask val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } // Set the (digit/2)th bit // of the number evenMask else { val += countOfNumbers(index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // For remaining positions, any // digit from [0-9] can be placed else { for ( var digit = 0; digit <= 9; ++digit) { // If digit is odd if ((digit & 1) != 0) { // Set the (digit/2)th // bit of oddMask val += countOfNumbers(index + 1, evenMask, oddMask | (1 << (digit / 2)), N); } else { // Set the (digit/2)th // bit of evenMask val += countOfNumbers(index + 1, evenMask | (1 << (digit / 2)), oddMask, N); } } } // Return the answer return val; } // Function to find number of N-digit // numbers which has equal count of // distinct odd and even digits function countNDigitNumber(N) { // Initialize dp array with -1 for ( var i = 0; i < 100; i++) { for ( var j = 0; j < (1 << 5); j++) { for ( var k = 0; k < (1 << 5); k++) { dp[i][j][k] = -1; } } } // Function Call document.write(countOfNumbers(1, 0, 0, N)); } // Driver code var N = 3; countNDigitNumber(N); // This code is contributed by gauravrajput1 </script> |
135
Time Complexity: O(N *10 * 25 * 25)
Auxiliary Space: O(N * 25 * 25)
Contact Us