Count pairs up to N having sum equal to their XOR | 2D array for memoization ; Recursive Function to count pairs ( x , y ) such that x + y = x ^ y ; If the string is traversed completely ; If the current subproblem is already calculated ; If bound = 1 and s [ i ] = = '0' , only ( 0 , 0 ) can be placed ; Otherwise ; Placing ( 0 , 1 ) and ( 1 , 0 ) are equivalent . Hence , multiply by 2. ; Place ( 0 , 0 ) at the current position . ; Return the answer ; Utility Function to convert N to its binary representation ; Function to count pairs ( x , y ) such that x + y = x ^ y ; Convert the number to equivalent binary representation ; Print answer returned by recursive function ; Driver code ; Input ; Function call
dp = [ [ - 1 for i in range ( 2 ) ] for j in range ( 1000 ) ] NEW_LINE def IsSumEqualsXor ( i , n , bound , s ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ i ] [ bound ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ bound ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( bound and s [ i ] == '0' ) : NEW_LINE INDENT ans = IsSumEqualsXor ( i + 1 , n , 1 , s ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = 2 * IsSumEqualsXor ( i + 1 , n , bound & ( s [ i ] == '1' ) , s ) NEW_LINE ans += IsSumEqualsXor ( i + 1 , n , 0 , s ) NEW_LINE DEDENT dp [ i ] [ bound ] = ans NEW_LINE return ans NEW_LINE DEDENT def convertToBinary ( n ) : NEW_LINE INDENT ans = [ ] NEW_LINE while ( n ) : NEW_LINE INDENT rem = chr ( n % 2 + 48 ) NEW_LINE ans . append ( rem ) NEW_LINE n //= 2 NEW_LINE DEDENT ans = ans [ : : - 1 ] NEW_LINE return ans NEW_LINE DEDENT def IsSumEqualsXorUtil ( N ) : NEW_LINE INDENT s = convertToBinary ( N ) NEW_LINE print ( IsSumEqualsXor ( 0 , len ( s ) , 1 , s ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 10 NEW_LINE IsSumEqualsXorUtil ( N ) NEW_LINE DEDENT