Count of N | 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 answer ; Driver Code ; Given number N ; Function Call
def countNums ( N ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 16 ) ] for j in range ( N ) ] ; NEW_LINE for i in range ( 1 , 10 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 1 ; NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT for k in range ( 0 , 16 ) : NEW_LINE INDENT xor = j ^ k ; NEW_LINE dp [ i ] [ xor ] += dp [ i - 1 ] [ k ] ; NEW_LINE DEDENT DEDENT DEDENT count = 0 ; NEW_LINE for i in range ( 0 , 10 ) : NEW_LINE INDENT count += dp [ N - 1 ] [ i ] ; NEW_LINE DEDENT print ( count ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 1 ; NEW_LINE countNums ( N ) ; NEW_LINE DEDENT