Count of N | C ++ program for the above approach ; Stores the dp - states ; Recursive Function to find number of N - digit numbers which has equal count of distinct odd & even digits ; If index is N + 1 ; Find the count of set bits in the evenMask ; Find the count of set bits in the 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 the state has already been computed ; If N = 1 , 0 can be also placed ; If digit is odd ; Set the ( digit / 2 ) th bit of the oddMask ; Set the ( digit / 2 ) th bit of the number evenMask ; For remaining positions , any digit from [ 0 - 9 ] can be placed ; If digit is odd ; Set the ( digit / 2 ) th bit of oddMask ; Set the ( digit / 2 ) th bit of evenMask ; Return the answer ; Function to find number of N - digit numbers which has equal count of distinct odd and even digits ; Initialize dp array with - 1 ; Function Call ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 1 << 5 ] [ 1 << 5 ] ; int countOfNumbers ( int index , int evenMask , int oddMask , int N ) { if ( index == N + 1 ) { int countOfEvenDigits = __builtin_popcount ( evenMask ) ; int countOfOddDigits = __builtin_popcount ( oddMask ) ; if ( countOfOddDigits == countOfEvenDigits ) { return 1 ; } return 0 ; } int & val = dp [ index ] [ evenMask ] [ oddMask ] ; if ( val != -1 ) return val ; val = 0 ; if ( index == 1 ) { for ( int digit = ( N == 1 ? 0 : 1 ) ; digit <= 9 ; ++ digit ) { if ( digit & 1 ) { val += countOfNumbers ( index + 1 , evenMask , oddMask | ( 1 << ( digit / 2 ) ) , N ) ; } else { val += countOfNumbers ( index + 1 , evenMask | ( 1 << ( digit / 2 ) ) , oddMask , N ) ; } } } else { for ( int digit = 0 ; digit <= 9 ; ++ digit ) { if ( digit & 1 ) { val += countOfNumbers ( index + 1 , evenMask , oddMask | ( 1 << ( digit / 2 ) ) , N ) ; } else { val += countOfNumbers ( index + 1 , evenMask | ( 1 << ( digit / 2 ) ) , oddMask , N ) ; } } } return val ; } void countNDigitNumber ( int N ) { memset ( dp , -1 , sizeof dp ) ; cout << countOfNumbers ( 1 , 0 , 0 , N ) ; } int main ( ) { int N = 3 ; countNDigitNumber ( N ) ; return 0 ; }