Given two integers S and X representing the sum and bitwise XOR respectively of two integers, the task is to find the count of all such possible pairs such that their sum is equal to S and bitwise XOR is equal to X.
Examples:
Input: S = 9, X = 5
Output: 4
Explanation: (2, 7), (3, 6), (6, 3), (7, 2) completely satisfies the given conditions.
It can also be seen that no other pair satisfy the given condition.
So the total possibility is 4.Input: S = 3, X = 3
Output: 4
Explanation: Only (1, 2), (2, 1), (3, 0) and (0, 3) satisfy the given condition.
Approach: The solution to the problem is based on the following observation:
Consider two numbers a and b. Their sum can be written as
a+b = (a XOR b) + (a AND b)*2The above can be proved as follows:
If two bits x and y are added, the carry (say c) will be (x AND y) and it is to one position left of the single bit. So, c = 2 * (x AND y)
The value of the rightmost bit (i.e., at the same position as of the single bits) will be (x XOR y)
Therefore x + y = (x XOR y) + 2 * (x AND y)So when adding a and b, this procedure repeats for each bit. Therefore it can be said that the sum will be
a+b = (a XOR b) + (a AND b)*2
S = X + 2*A where A is the bitwise AND of the two numbers.
A = (S – X)/2
Based on the above observation the count can be obtained from the bit values of A and X as per the following case
- If the ith bit of X and A both are 0, then there is only one possible pair for that bit position.
- If the ith bit of X is 1 and of A is 0, then there are two possible pairs for that bit position.
- If the ith bit of X is 0 and of A is 1, then there is only one possible pair for that bit position.
- There cannot be a situation where ith bit at X is 1 and ith bit of A is also 1.
According to the multiplication principle of permutation, to get the number of possible pairs satisfying the given condition just multiply all possibilities. Follow the steps mentioned below to implement the idea:
- Find bitwise AND of two numbers by using the above formula.
- If it is not an integer then no solution exist
- Otherwise for given value of the XOR (X) and AND (say A) check for each bit
- Find the number of possibilities for that bit using the above cases.
- Multiply these possibilities with the final answer.
- At the end the total number possibilities calculated as per the above conditions is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate// total number of possible pairsint count_all_possible_pair(int sum_value, int xor_value){ double and_value = ((sum_value - xor_value) / 2.0); // If and value is not an integer // then no pair is possible int check = and_value; if (check != and_value) return 0; int count = 1; // Traversing the bits of the sum_value // from MSB position for (int i = 1; i <= 32; i++) { int and_bit = (check >> i) & 1; int xor_bit = (xor_value >> i) & 1; // If both the bit is 0, only 1 possibility if (and_bit == 0 && xor_bit == 0) count = count * 1; // If Xor bit is 0 and And bit 1, // then only 1 possibility else if (xor_bit == 0 && and_bit == 1) count = count * 1; // If Xor bit is 1, And bit is 0, // then there are 2 possibilities else if (xor_bit == 1 && and_bit == 0) count = count * 2; // If Xor bit and And bit both 1, // no such case is possible else return 0; } // Return the count of possible pairs return count;}// Driver codeint main(){ int S = 9, X = 5; // Function call cout << count_all_possible_pair(S, X); return 0;} |
Java
// Java code to implement the approachpublic class GFG { // Function to calculate // total number of possible pairs static int count_all_possible_pair(int sum_value, int xor_value) { double and_value = ((sum_value - xor_value) / 2.0); // If and value is not an integer // then no pair is possible int check = (int)and_value; if (check != and_value) return 0; int count = 1; // Traversing the bits of the sum_value // from MSB position for (int i = 1; i <= 32; i++) { int and_bit = (check >> i) & 1; int xor_bit = (xor_value >> i) & 1; // If both the bit is 0, only 1 possibility if (and_bit == 0 && xor_bit == 0) count = count * 1; // If Xor bit is 0 and And bit 1, // then only 1 possibility else if (xor_bit == 0 && and_bit == 1) count = count * 1; // If Xor bit is 1, And bit is 0, // then there are 2 possibilities else if (xor_bit == 1 && and_bit == 0) count = count * 2; // If Xor bit and And bit both 1, // no such case is possible else return 0; } // Return the count of possible pairs return count; } // Driver code public static void main (String[] args) { int S = 9, X = 5; // Function call System.out.println(count_all_possible_pair(S, X)); }}// This code is contributed by AnkThon |
Python3
# Python3 code to implement the approach# Function to calculate# total number of possible pairsdef count_all_possible_pair(sum_value, xor_value) : and_value = ((sum_value - xor_value) / 2.0); # If and value is not an integer # then no pair is possible check = int(and_value); if (check != and_value) : return 0; count = 1; # Traversing the bits of the sum_value # from MSB position for i in range(1 , 33) : and_bit = ((check >> i) & 1); xor_bit = ((xor_value >> i) & 1); # If both the bit is 0, only 1 possibility if (and_bit == 0 and xor_bit == 0) : count = count * 1; # If Xor bit is 0 and And bit 1, # then only 1 possibility elif (xor_bit == 0 and and_bit == 1) : count = count * 2; # If Xor bit is 1, And bit is 0, # then there are 2 possibilities elif (xor_bit == 1 and and_bit == 0) : count = count * 2; # If Xor bit and And bit both 1, # no such case is possible else : return 0; # Return the count of possible pairs return count;# Driver codeif __name__ == "__main__" : S = 9; X = 5; # Function call print(count_all_possible_pair(S, X)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG { // Function to calculate // total number of possible pairs static int count_all_possible_pair(int sum_value, int xor_value) { double and_value = ((sum_value - xor_value) / 2.0); // If and value is not an integer // then no pair is possible int check = (int)and_value; if (check != and_value) return 0; int count = 1; // Traversing the bits of the sum_value // from MSB position for (int i = 1; i <= 32; i++) { int and_bit = (check >> i) & 1; int xor_bit = (xor_value >> i) & 1; Console.WriteLine("value:" + i); Console.WriteLine(and_bit+"test"+xor_bit); // If both the bit is 0, only 1 possibility if (and_bit == 0 && xor_bit == 0) count = count * 1; // If Xor bit is 0 and And bit 1, // then only 1 possibility else if (xor_bit == 0 && and_bit == 1) count = count * 1; // If Xor bit is 1, And bit is 0, // then there are 2 possibilities else if (xor_bit == 1 && and_bit == 0) count = count * 2; // If Xor bit and And bit both 1, // no such case is possible else return 0; } // Return the count of possible pairs return count; } // Driver code public static void Main () { int S = 9, X = 5; // Function call Console.Write(count_all_possible_pair(S, X)); }}// This code is contributed by gfgking |
Javascript
// JavaScript code to implement the approach// Function to calculate// total number of possible pairsfunction count_all_possible_pair(sum_value, xor_value){ var and_value = Math.floor((sum_value - xor_value) / 2.0); // If and value is not an integer // then no pair is possible var check = and_value; if (check != and_value) return 0; var count = 1; // Traversing the bits of the sum_value // from MSB position for (var i = 1; i <= 32; i++) { var and_bit = (check >> i) & 1; var xor_bit = (xor_value >> i) & 1; // If both the bit is 0, only 1 possibility if (and_bit == 0 && xor_bit == 0) count = count * 1; // If Xor bit is 0 and And bit 1, // then only 1 possibility else if (xor_bit == 0 && and_bit == 1) count = count * 1; // If Xor bit is 1, And bit is 0, // then there are 2 possibilities else if (xor_bit == 1 && and_bit == 0) count = count * 2; // If Xor bit and And bit both 1, // no such case is possible else return 0; } // Return the count of possible pairs return count;}// Driver codevar S = 9;var X = 5;// Function calldocument.write(count_all_possible_pair(S, X));// This code is contributed by phasing17 |
4
Time Complexity: O(N) where N is the number of bits in the given sum S
Auxiliary Space: O(1)
