Count of N | C # program for the above approach ; Stores the dp - states ; Returns number of set bits in a number ; 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
using System ; class GFG { static int [ , , ] dp = new int [ 100 , 1 << 5 , 1 << 5 ] ; 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 ; } static 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 ) != 0 ) { 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 ) != 0 ) { val += countOfNumbers ( index + 1 , evenMask , oddMask | ( 1 << ( digit / 2 ) ) , N ) ; } else { val += countOfNumbers ( index + 1 , evenMask | ( 1 << ( digit / 2 ) ) , oddMask , N ) ; } } } return val ; } static void countNDigitNumber ( int N ) { 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 ; } } } Console . Write ( countOfNumbers ( 1 , 0 , 0 , N ) ) ; } public static void Main ( ) { int N = 3 ; countNDigitNumber ( N ) ; } }