Count ways to generate pairs having Bitwise XOR and Bitwise AND equal to X and Y respectively
Given two integers X and Y, the task is to find the total number of ways to generate a pair of integers A and B such that Bitwise XOR and Bitwise AND between A and B is X and Y respectively
Examples:
Input: X = 2, Y = 5
Output: 2
Explanation:
The two possible pairs are (5, 7) and (7, 5).
Pair 1: (5, 7)
Bitwise AND = 5 & 7 = 2
Bitwise XOR = 5 ^ 7 = 5
Pair 2: (7, 5)
Bitwise AND = 7 & 5 = 2
Bitwise XOR = 7 ^ 5 = 5Input: X = 7, Y = 5
Output: 0
Naive Approach: The simplest approach to solve the problem is to choose the maximum among X and Y and set all its bits and then check all possible pairs from 0 to that maximum number, say M. If for any pair of A and B, A & B and A?B becomes equal to X and Y respectively, then increment the count. Print the final value of count after checking for all possible pairs.
Time Complexity: O(M2), where M = max(X,Y)
Auxiliary Space: O(1)
Efficient Approach: The idea is to generate all possible combinations of bits at each position. There are 4 possibilities for the ith bit in X and Y which are as follows:
- If Xi = 0 and Yi = 1, then Ai = 1 and Bi = 1.
- If Xi = 1 and Yi = 1, then no possible bit assignment exist.
- If Xi = 0 and Yi = 0 then Ai = 0 and Bi = 0.
- If Xi = 1 and Yi = 0 then Ai = 0 and Bi = 1 or Ai = 1 and Bi = 0, where Ai, Bi, Xi, and Yi represent ith bit in each of them.
Follow the steps below to solve the problem:
- Initialize the counter as 1.
- For the ith bit, if Xi and Yi are equal to 1, then print 0.
- If at ith bit, Xi is 1 and Yi is 0 then multiply the counter by 2 as there are 2 options.
- After that, divide X and Y each time by 2.
- Repeat the above steps for every ith bit until both of them become 0 and print the value of the counter.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to return the count of // possible pairs of A and B whose // Bitwise XOR is X and Y respectively int countOfPairs( int x, int y) { // Stores the count of pairs int counter = 1; // Iterate till any bit are set while (x || y) { // Extract i-th bit // of X and Y int bit1 = x % 2; int bit2 = y % 2; // Divide X and Y by 2 x >>= 1; y >>= 1; // If Xi = 1 and Yi = 2, // multiply counter by 2 if (bit1 == 1 and bit2 == 0) { // Increase required count counter *= 2; continue ; } // If Xi =1 and Yi = 1 if (bit1 & bit2) { // No answer exists counter = 0; break ; } } // Return the final count return counter; } // Driver Code int main() { // Given X and Y int X = 2, Y = 5; // Function Call cout << countOfPairs(X, Y); return 0; } |
Java
// Java program for // the above approach import java.util.*; class GFG{ // Function to return the count of // possible pairs of A and B whose // Bitwise XOR is X and Y respectively static int countOfPairs( int x, int y) { // Stores the count of pairs int counter = 1 ; // Iterate till any bit are set while (x > 0 || y > 0 ) { // Extract i-th bit // of X and Y int bit1 = x % 2 ; int bit2 = y % 2 ; // Divide X and Y by 2 x >>= 1 ; y >>= 1 ; // If Xi = 1 and Yi = 2, // multiply counter by 2 if (bit1 == 1 && bit2 == 0 ) { // Increase required count counter *= 2 ; continue ; } // If Xi =1 and Yi = 1 if ((bit1 & bit2) > 0 ) { // No answer exists counter = 0 ; break ; } } // Return the final count return counter; } // Driver Code public static void main(String[] args) { // Given X and Y int X = 2 , Y = 5 ; // Function Call System.out.print(countOfPairs(X, Y)); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach # Function to return the count of # possible pairs of A and B whose # Bitwise XOR is X and Y respectively def countOfPairs(x, y): # Stores the count of pairs counter = 1 # Iterate till any bit are set while (x or y): # Extract i-th bit # of X and Y bit1 = x % 2 bit2 = y % 2 # Divide X and Y by 2 x >> = 1 y >> = 1 # If Xi = 1 and Yi = 2, # multiply counter by 2 if (bit1 = = 1 and bit2 = = 0 ): # Increase required count counter * = 2 continue # If Xi =1 and Yi = 1 if (bit1 & bit2): # No answer exists counter = 0 break # Return the final count return counter # Driver Code # Given X and Y X = 2 Y = 5 # Function call print (countOfPairs(X, Y)) # This code is contributed by Shivam Singh |
C#
// C# program for // the above approach using System; class GFG{ // Function to return the count of // possible pairs of A and B whose // Bitwise XOR is X and Y respectively static int countOfPairs( int x, int y) { // Stores the count of pairs int counter = 1; // Iterate till any bit are set while (x > 0 || y > 0) { // Extract i-th bit // of X and Y int bit1 = x % 2; int bit2 = y % 2; // Divide X and Y by 2 x >>= 1; y >>= 1; // If Xi = 1 and Yi = 2, // multiply counter by 2 if (bit1 == 1 && bit2 == 0) { // Increase required count counter *= 2; continue ; } // If Xi =1 and Yi = 1 if ((bit1 & bit2) > 0) { // No answer exists counter = 0; break ; } } // Return the readonly count return counter; } // Driver Code public static void Main(String[] args) { // Given X and Y int X = 2, Y = 5; // Function Call Console.Write(countOfPairs(X, Y)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program for // the above approach // Function to return the count of // possible pairs of A and B whose // Bitwise XOR is X and Y respectively function countOfPairs(x, y) { // Stores the count of pairs let counter = 1; // Iterate till any bit are set while (x > 0 || y > 0) { // Extract i-th bit // of X and Y let bit1 = x % 2; let bit2 = y % 2; // Divide X and Y by 2 x >>= 1; y >>= 1; // If Xi = 1 and Yi = 2, // multiply counter by 2 if (bit1 == 1 && bit2 == 0) { // Increase required count counter *= 2; continue ; } // If Xi =1 and Yi = 1 if ((bit1 & bit2) > 0) { // No answer exists counter = 0; break ; } } // Return the final count return counter; } // Driver code // Given X and Y let X = 2, Y = 5; // Function Call document.write(countOfPairs(X, Y)); </script> |
2
Time Complexity: O(log M), where M = max(X,Y), as we are using a loop to traverse and each time we are decrementing by floor division of 2.
Auxiliary Space: O(1), as we are not using any extra space.