Count pairs up to N having sum equal to their XOR | C ++ program for the above approach ; 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 ; Initialize dp array with - 1. ; Print answer returned by recursive function ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1000 ] [ 2 ] ; int IsSumEqualsXor ( int i , int n , bool bound , string & s ) { if ( i == n ) return 1 ; if ( dp [ i ] [ bound ] != -1 ) return dp [ i ] [ bound ] ; int ans = 0 ; if ( bound and s [ i ] == '0' ) { ans = IsSumEqualsXor ( i + 1 , n , 1 , s ) ; } else { ans = 2 * IsSumEqualsXor ( i + 1 , n , bound & ( s [ i ] == '1' ) , s ) ; ans += IsSumEqualsXor ( i + 1 , n , 0 , s ) ; } return dp [ i ] [ bound ] = ans ; } string convertToBinary ( int n ) { string ans ; while ( n ) { char rem = char ( n % 2 + '0' ) ; ans . push_back ( rem ) ; n /= 2 ; } reverse ( ans . begin ( ) , ans . end ( ) ) ; return ans ; } void IsSumEqualsXorUtil ( int N ) { string s = convertToBinary ( N ) ; memset ( dp , -1 , sizeof dp ) ; cout << IsSumEqualsXor ( 0 , s . size ( ) , 1 , s ) << endl ; } int main ( ) { int N = 10 ; IsSumEqualsXorUtil ( N ) ; return 0 ; }