Find the value of X and Y such that X Bitwise XOR Y equals to (X+Y)/2
Given an integer N, representing X β Y where β represents Bitwise XOR, the task is to find the value of X and Y such that X β Y = (X+Y)/2. If no possible value of X and Y exist, print -1.
Examples:
Input: N = 20
Output: X = 30, Y = 10
Explanation: X β Y = 20 and (X+Y)/2 = 20Input: N = 6
Output: -1
Explanation: No valid pair of X and Y exists.
Approach: The problem can be solved using the following approach:
Since it is given X β Y= (X + Y)/2,
=> 2 * (X β Y) = X + Y (Equation 1)
We know, A + B = A β B + 2 * (A & B), where & is the Bitwise AND operator
Thus Equation 1 can be modified to:
X β Y= 2 * (X & Y)
From the above equation we can say that X β Y should be even otherwise answer wonβt exist. Let N =X β Y and M= (X β Y)/2, i.e., N represents Bitwise XOR and M represents Bitwise AND. It can also be observed that N and M cannot have a particular bit set simultaneously because if a particular bit is set in both N and M, then it would mean that the Bitwise AND as well as Bitwise XOR both have the bit as set which is impossible. Now, we will find X and Y bit by bit. For an ith bit, we will have 3 cases:
- Case 1: N have ith bit set: In this case, either of X or Y should have the ith bit set since N is bitwise XOR of X and Y. So will add (1<<i) to X.
- Case 2: M have ith bit set: In this case, both of X and Y should have the ith bit set since M is bitwise AND of X and Y. So will add (1<<i) to X and Y.
- Case 3: Neither N and M have ith bit set: In this case, both of X and Y will not have the ith bit set.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; void solve( int N) { // (X XOR Y) should be an even number if (N % 2) { cout << -1 << "\n" ; } // M = X & Y int M = N / 2; // No bit should be set in both M and N if ((N & M) != 0) { cout << -1 << "\n" ; } int X = 0, Y = 0; for ( int i = 0; i < 31; i++) { // If ith bit of (X XOR Y) is set if ((N & (1 << i)) != 0) { X = X + (1 << i); } // If ith bit of (X AND Y) is set else if ((M & (1 << i)) != 0) { X = X + (1 << i); Y = Y + (1 << i); } } cout << X << " " << Y << "\n" ; } // Driver Code int main() { int N = 20; solve(N); } |
Java
public class Main { public static void solve( int N) { // (X XOR Y) should be an even number if (N % 2 != 0 ) { System.out.println(- 1 ); return ; } // M = X & Y int M = N / 2 ; // No bit should be set in both M and N if ((N & M) != 0 ) { System.out.println(- 1 ); return ; } int X = 0 , Y = 0 ; for ( int i = 0 ; i < 31 ; i++) { // If ith bit of (X XOR Y) is set if ((N & ( 1 << i)) != 0 ) { X = X + ( 1 << i); } // If ith bit of (X AND Y) is set else if ((M & ( 1 << i)) != 0 ) { X = X + ( 1 << i); Y = Y + ( 1 << i); } } System.out.println(X + " " + Y); } // Driver Code public static void main(String[] args) { int N = 20 ; solve(N); } } // This code is contributed by rambabuguphka |
Python3
def solve(N): # (X XOR Y) should be an even number if N % 2 : print ( - 1 ) return # M = X & Y M = N / / 2 # No bit should be set in both M and N if N & M: print ( - 1 ) return X, Y = 0 , 0 for i in range ( 31 ): # If ith bit of (X XOR Y) is set if N & ( 1 << i): X = X + ( 1 << i) # If ith bit of (X AND Y) is set elif M & ( 1 << i): X = X + ( 1 << i) Y = Y + ( 1 << i) print (X, Y) # Driver Code N = 20 solve(N) |
C#
using System; public class Program { public static void Solve( int N) { // (X XOR Y) should be an even number if (N % 2 != 0) { Console.WriteLine(-1); return ; } // M = X & Y int M = N / 2; // No bit should be set in both M and N if ((N & M) != 0) { Console.WriteLine(-1); return ; } int X = 0, Y = 0; for ( int i = 0; i < 31; i++) { // If ith bit of (X XOR Y) is set if ((N & (1 << i)) != 0) { X = X + (1 << i); } // If ith bit of (X AND Y) is set else if ((M & (1 << i)) != 0) { X = X + (1 << i); Y = Y + (1 << i); } } Console.WriteLine(X + " " + Y); } // Entry point public static void Main( string [] args) { int N = 20; Solve(N); } } |
Javascript
// javaScript code for the above approach function solve(N) { // (X XOR Y) should be an even number if (N % 2) { console.log(-1); return ; } // M = X & Y let M = N / 2; // No bit should be set in both M and N if ((N & M) !== 0) { console.log(-1); return ; } let X = 0, Y = 0; for (let i = 0; i < 31; i++) { // If ith bit of (X XOR Y) is set if ((N & (1 << i)) !== 0) { X = X + (1 << i); } // If ith bit of (X AND Y) is set else if ((M & (1 << i)) !== 0) { X = X + (1 << i); Y = Y + (1 << i); } } console.log(X + " " + Y); } // Driver Code let N = 20; solve(N); |
30 10
Time Complexity: O(log N), where N is the input number ( X β Y )
Auxiliary Space: O(1)