Given an integer N, the task is to count the number of pairs (X, Y) such that X + Y = X ^ Y and X + Y ? N.
Note: ^ denotes Bitwise xor.
Examples:
Input: N = 3
Output: 9
Explanation: The pairs satisfying the given conditions are {{0, 0}, {0, 1}, {1, 0}, {0, 2}, {2, 0}, {3, 0}, {0, 3}, {2, 1}, {1, 2}}Input: N = 10
Output: 37
Naive Approach: The simplest approach is to generate all possible pairs (X, Y) and check if the conditions X + Y = X ^ Y and X + Y ? N are satisfied or not.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the observation that X+Y ? X ^ Y for any value of X and Y. Consider the binary representation of X and Y. Let bit(X, pos) and bit(Y, pos) be the bits corresponding to X and Y at some fixed position pos. The condition X+Y = X^Y will be only satisfied if {bit(X, pos), bit(Y, pos)} ? {{1, 0}, {0, 1}, {0, 0}}. In other words, both X and Y cannot have set bits at the same positions.
In the efficient approach, the problem can be solved using Dynamic Programming. The problems have overlapping subproblems and optimal substructure. The subproblems are stored in a dp[][] table using memoization where dp[i][bound] stores the answer from the ‘i’th position to the end and bound is a boolean variable to ensure that the sum of numbers does not exceed N.
- Convert the limit N into its binary representation. Store the binary representation in a string, say S, so that iterating only over the length of the string and not the actual limit will be sufficient.
- Define a recursive function IsSumEqualsXor(i, bound) by performing the following steps.
- Check the base cases, if i == length of S then return 1, as a valid pair has been formed.
- If the result of the state dp[i][bound] has already been computed, then return the state dp[i][bound].
- At the current position i, any of the three pairs among {{0, 0}, {0, 1}, {1, 0}} can be assigned by checking few conditions. They are
- If the bound is true and the current character in S i.e S[i] is ‘0’ then, only {0, 0} can be placed as a valid pair in the current position. That is done to ensure that the sum does not exceed N.
- Otherwise, any pair among {{0, 0}, {0, 1}, {1, 0}} can be placed and bound is set to true or false accordingly.
- After placing a valid pair in the current position, recursively call the IsSumEqualsXor function for the element at index (i + 1).
- Return the sum of all possible valid placements of digits as the answer.
Below is the implementation of the above approach :
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // 2D array for memoization int dp[1000][2]; // Recursive Function to count pairs // (x, y) such that x+y = x^y int IsSumEqualsXor( int i, int n, bool bound, string& s) { // If the string is traversed completely if (i == n) return 1; // If the current subproblem // is already calculated if (dp[i][bound] != -1) return dp[i][bound]; int ans = 0; // If bound = 1 and s[i] == '0', // only (0, 0) can be placed if (bound and s[i] == '0' ) { ans = IsSumEqualsXor(i + 1, n, 1, s); } // Otherwise else { // Placing (0, 1) and (1, 0) are // equivalent. Hence, multiply by 2. ans = 2 * IsSumEqualsXor(i + 1, n, bound & (s[i] == '1' ), s); // Place (0, 0) at the current position. ans += IsSumEqualsXor(i + 1, n, 0, s); } // Return the answer return dp[i][bound] = ans; } // Utility Function to convert N // to its binary representation 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; } // Function to count pairs (x, y) // such that x + y = x^y void IsSumEqualsXorUtil( int N) { // Convert the number to // equivalent binary representation string s = convertToBinary(N); // Initialize dp array with -1. memset (dp, -1, sizeof dp); // Print answer returned by recursive function cout << IsSumEqualsXor(0, s.size(), 1, s) << endl; } // Driver code int main() { // Input int N = 10; // Function call IsSumEqualsXorUtil(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // 2D array for memoization static int [][]dp = new int [ 1000 ][ 2 ]; // Recursive Function to count pairs // (x, y) such that x+y = x^y static int IsSumEqualsXor( int i, int n, int bound, char [] s) { // If the String is traversed completely if (i == n) return 1 ; // If the current subproblem // is already calculated if (dp[i][bound] != - 1 ) return dp[i][bound]; int ans = 0 ; // If bound = 1 and s[i] == '0', // only (0, 0) can be placed if (bound!= 0 && s[i] == '0' ) { ans = IsSumEqualsXor(i + 1 , n, 1 , s); } // Otherwise else { // Placing (0, 1) and (1, 0) are // equivalent. Hence, multiply by 2. ans = 2 * IsSumEqualsXor(i + 1 , n, bound!= 0 & (s[i] == '1' )? 1 : 0 , s); // Place (0, 0) at the current position. ans += IsSumEqualsXor(i + 1 , n, 0 , s); } // Return the answer 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); } // Utility Function to convert N // to its binary representation 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; } // Function to count pairs (x, y) // such that x + y = x^y static void IsSumEqualsXorUtil( int N) { // Convert the number to // equivalent binary representation String s = convertToBinary(N); // Initialize dp array with -1. for ( int i = 0 ; i < dp.length; i++) { for ( int j = 0 ; j < dp[ 0 ].length; j++) { dp[i][j] = - 1 ; } } // Print answer returned by recursive function System.out.print(IsSumEqualsXor( 0 , s.length(), 1 , s.toCharArray()) + "\n" ); } // Driver code public static void main(String[] args) { // Input int N = 10 ; // Function call IsSumEqualsXorUtil(N); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # 2D array for memoization dp = [[ - 1 for i in range ( 2 )] for j in range ( 1000 )] # Recursive Function to count pairs # (x, y) such that x+y = x^y def IsSumEqualsXor(i, n, bound, s): # If the string is traversed completely if (i = = n): return 1 # If the current subproblem # is already calculated if (dp[i][bound] ! = - 1 ): return dp[i][bound] ans = 0 # If bound = 1 and s[i] == '0', # only (0, 0) can be placed if (bound and s[i] = = '0' ): ans = IsSumEqualsXor(i + 1 , n, 1 , s) # Otherwise else : # Placing (0, 1) and (1, 0) are # equivalent. Hence, multiply by 2. ans = 2 * IsSumEqualsXor( i + 1 , n, bound & (s[i] = = '1' ), s) # Place (0, 0) at the current position. ans + = IsSumEqualsXor(i + 1 , n, 0 , s) dp[i][bound] = ans # Return the answer return ans # Utility Function to convert N # to its binary representation def convertToBinary(n): ans = [] while (n): rem = chr (n % 2 + 48 ) ans.append(rem) n / / = 2 ans = ans[:: - 1 ] return ans # Function to count pairs (x, y) # such that x + y = x^y def IsSumEqualsXorUtil(N): # Convert the number to # equivalent binary representation s = convertToBinary(N) # Print answer returned by recursive function print (IsSumEqualsXor( 0 , len (s), 1 , s)) # Driver code if __name__ = = '__main__' : # Input N = 10 # Function call IsSumEqualsXorUtil(N) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG{ // 2D array for memoization static int [,]dp = new int [1000, 2]; // Recursive Function to count pairs // (x, y) such that x+y = x^y static int IsSumEqualsXor( int i, int n, int bound, char [] s) { // If the String is traversed completely if (i == n) return 1; // If the current subproblem // is already calculated if (dp[i,bound] != -1) return dp[i,bound]; int ans = 0; // If bound = 1 and s[i] == '0', // only (0, 0) can be placed if (bound != 0 && s[i] == '0' ) { ans = IsSumEqualsXor(i + 1, n, 1, s); } // Otherwise else { // Placing (0, 1) and (1, 0) are // equivalent. Hence, multiply by 2. ans = 2 * IsSumEqualsXor(i + 1, n, bound != 0 & (s[i] == '1' ) ? 1 : 0, s); // Place (0, 0) at the current position. ans += IsSumEqualsXor(i + 1, n, 0, s); } // Return the answer 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.Join( "" , a); } // Utility Function to convert N // to its binary representation 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; } // Function to count pairs (x, y) // such that x + y = x^y static void IsSumEqualsXorUtil( int N) { // Convert the number to // equivalent binary representation String s = convertToBinary(N); // Initialize dp array with -1. for ( int i = 0; i < dp.GetLength(0); i++) { for ( int j = 0; j < dp.GetLength(1); j++) { dp[i, j] = -1; } } // Print answer returned by recursive function Console.Write(IsSumEqualsXor(0, s.Length, 1, s.ToCharArray()) + "\n" ); } // Driver code public static void Main(String[] args) { // Input int N = 10; // Function call IsSumEqualsXorUtil(N); } } // This code is contributed by umadevi9616 |
Javascript
<script> // Javascript program for the above approach // 2D array for memoization let dp = new Array(1000); for (let i = 0; i < 1000; i++) { dp[i] = new Array(2); } // Recursive Function to count pairs // (x, y) such that x+y = x^y function IsSumEqualsXor(i, n, bound, s) { // If the String is traversed completely if (i == n) return 1; // If the current subproblem // is already calculated if (dp[i][bound] != -1) return dp[i][bound]; let ans = 0; // If bound = 1 and s[i] == '0', // only (0, 0) can be placed if (bound!=0 && s[i] == '0' ) { ans = IsSumEqualsXor(i + 1, n, 1, s); } // Otherwise else { // Placing (0, 1) and (1, 0) are // equivalent. Hence, multiply by 2. ans = 2 * IsSumEqualsXor(i + 1, n, bound!=0 & (s[i] == '1' )?1:0, s); // Place (0, 0) at the current position. ans += IsSumEqualsXor(i + 1, n, 0, s); } // Return the answer 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( "" ); } // Utility Function to convert N // to its binary representation 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 to count pairs (x, y) // such that x + y = x^y function IsSumEqualsXorUtil(N) { // Convert the number to // equivalent binary representation let s = convertToBinary(N); // Initialize dp array with -1. for (let i = 0; i < dp.length; i++) { for (let j = 0; j < dp[0].length; j++) { dp[i][j] = -1; } } // Print answer returned by recursive function document.write(IsSumEqualsXor(0, s.length, 1, s.split( '' )) + "</br>" ); } // Input let N = 10; // Function call IsSumEqualsXorUtil(N); // This code is contributed by suresh07. </script> |
37
Time Complexity: O(Log2N)
Auxiliary Space: O(Log2N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!