Count of N | C ++ program for the above approach ; Function to find count of N - digit numbers with single digit XOR ; dp [ i ] [ j ] stores the number of i - digit numbers with XOR equal to j ; For 1 - 9 store the value ; Iterate till N ; Calculate XOR ; Store in DP table ; Initialize count ; Print the answer ; Driver Code ; Given number N ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countNums ( int N ) { int dp [ N ] [ 16 ] ; memset ( dp , 0 , sizeof ( dp [ 0 ] [ 0 ] ) * N * 16 ) ; for ( int i = 1 ; i <= 9 ; i ++ ) dp [ 0 ] [ i ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < 10 ; j ++ ) { for ( int k = 0 ; k < 16 ; k ++ ) { int xo = j ^ k ; dp [ i ] [ xo ] += dp [ i - 1 ] [ k ] ; } } } int count = 0 ; for ( int i = 0 ; i < 10 ; i ++ ) count += dp [ N - 1 ] [ i ] ; cout << ( count ) << endl ; } int main ( ) { int N = 1 ; countNums ( N ) ; }