Count pairs up to N having sum equal to their XOR | Java 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
import java . util . * ; class GFG { static int [ ] [ ] dp = new int [ 1000 ] [ 2 ] ; static int IsSumEqualsXor ( int i , int n , int bound , char [ ] s ) { if ( i == n ) return 1 ; if ( dp [ i ] [ bound ] != - 1 ) return dp [ i ] [ bound ] ; int ans = 0 ; if ( bound != 0 && s [ i ] == '0' ) { ans = IsSumEqualsXor ( i + 1 , n , 1 , s ) ; } else { ans = 2 * IsSumEqualsXor ( i + 1 , n , bound != 0 & ( s [ i ] == '1' ) ? 1 : 0 , s ) ; ans += IsSumEqualsXor ( i + 1 , n , 0 , s ) ; } return dp [ i ] [ bound ] = ans ; } static String reverse ( String input ) { char [ ] a = input . toCharArray ( ) ; int l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . valueOf ( a ) ; } static String convertToBinary ( int n ) { String ans = " " ; while ( n > 0 ) { char rem = ( char ) ( n % 2 + '0' ) ; ans += ( rem ) ; n /= 2 ; } ans = reverse ( ans ) ; return ans ; } static void IsSumEqualsXorUtil ( int N ) { String s = convertToBinary ( N ) ; for ( int i = 0 ; i < dp . length ; i ++ ) { for ( int j = 0 ; j < dp [ 0 ] . length ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . print ( IsSumEqualsXor ( 0 , s . length ( ) , 1 , s . toCharArray ( ) ) + "NEW_LINE"); } public static void main ( String [ ] args ) { int N = 10 ; IsSumEqualsXorUtil ( N ) ; } }