Given the sum and xor of two numbers X and Y s.t. sum and xor , we need to find the numbers minimizing the value of X.
Input : S = 17 X = 13 Output : a = 2 b = 15 Input : S = 1870807699 X = 259801747 Output : a = 805502976 b = 1065304723 Input : S = 1639 X = 1176 Output : No such numbers exist
X ==> XOR of two numbers
S ==> Sum of two numbers
X[i] ==> Value of i-th bit in X
S[i] ==> Value of i-th bit in S
A simple solution is to generate all possible pairs with given XOR. To generate all pairs, we can follow below rules.
- If X[i] is 1, then both a[i] and b[i] should be different, we have two cases.
- If X[i] is 0, then both a[i] and b[i] should be same. we have two cases.
- If X[i] = 0 and A[i] = 0, then a[i] = b[i] = 0. Only one possibility for this bit.
- If X[i] = 0 and A[i] = 1, then a[i] = b[i] = 1. Only one possibility for this bit.
- If X[i] = 1 and A[i] = 0, then (a[i] = 1 and b[i] = 0) or (a[i] = 0 and b[i] = 1), we can pick any of the two.
- If X[i] = 1 and A[i] = 1, result not possible (Note X[i] = 1 means different bits)
- Find two numbers from their sum and XOR | Set 2
- Count pairs from 1 to N such that their Sum is divisible by their XOR
- Count ordered pairs of positive numbers such that their sum is S and XOR is K
- XOR of two numbers after making length of their binary representations equal
- Find a number M < N such that difference between their XOR and AND is maximum
- Find XOR of two number without using XOR operator
- Find K numbers with sum equal to N and sum of their squares maximized
- Minimum flips in two binary arrays so that their XOR is equal to another array
- Program to find if two numbers and their AM and HM are present in an array using STL
- Find number of pairs in an array such that their XOR is 0
- Find two numbers made up of a given digit such that their difference is divisible by N
- Find two distinct numbers such that their LCM lies in given range
- Largest number M having bit count of N such that difference between their OR and XOR value is maximized
- Given a set, find XOR of the XOR's of all subsets.
- Count all Quadruples from four arrays such that their XOR equals to 'x'
- Rearrange given binary strings to maximize their Bitwise XOR value
- Count nodes having Bitwise XOR of all edges in their path from the root equal to K
- Find Two Missing Numbers | Set 2 (XOR based solution)
- Print numbers with digits 0 and 1 only such that their sum is N
- Split N natural numbers into two sets having GCD of their sums greater than 1
So we generate 2^n possible pairs where n is number of bits in X. Then for every pair, we check if its sum is S or not.
An efficient solution is based on below fact.
S = X + 2*A
where A = a AND b
We can verify above fact using the sum process. In sum, whenever we see both bits 1 (i.e., AND is 1), we make resultant bit 0 and add 1 as carry, which means every bit in AND is left shifted by 1 OR value of AND is multiplied by 2 and added.
So we can find A = (S – X)/2.
Once we find A, we can find all bits of ‘a’ and ‘b’ using below rules.
Let the summation be S and XOR be X.
Below is the implementation of above approach:
a = 15 b = 2
Time complexity of the above approach where b is number of bits in S.
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to firstname.lastname@example.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.