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 ; Initialize dp array with - 1. ; Print answer returned by recursive function ; Input ; Function call
let dp = new Array ( 1000 ) ; for ( let i = 0 ; i < 1000 ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } function IsSumEqualsXor ( i , n , bound , s ) { if ( i == n ) return 1 ; if ( dp [ i ] [ bound ] != - 1 ) return dp [ i ] [ bound ] ; let ans = 0 ; if ( bound != 0 && s [ i ] == ' ' ) { ans = IsSumEqualsXor ( i + 1 , n , 1 , s ) ; } else { ans = 2 * IsSumEqualsXor ( i + 1 , n , bound != 0 & ( s [ i ] == ' ' ) ? 1 : 0 , s ) ; ans += IsSumEqualsXor ( i + 1 , n , 0 , s ) ; } dp [ i ] [ bound ] = ans return dp [ i ] [ bound ] ; } function reverse ( input ) { let a = input . split ( ' ' ) ; let l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { let temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return a . join ( " " ) ; } function convertToBinary ( n ) { let ans = " " ; while ( n > 0 ) { let rem = String . fromCharCode ( n % 2 + 48 ) ; ans += ( rem ) ; n = parseInt ( n / 2 , 10 ) ; } ans = reverse ( ans ) ; return ans ; } function IsSumEqualsXorUtil ( N ) { let s = convertToBinary ( N ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { for ( let j = 0 ; j < dp [ 0 ] . length ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( IsSumEqualsXor ( 0 , s . length , 1 , s . split ( ' ' ) ) + " " ) ; } let N = 10 ; IsSumEqualsXorUtil ( N ) ;