The ‘Minimum X (xor) A’ problem is one of the popular problems that can be solved using the concept of Bit Manipulation. Bit manipulation is one of the important topics for technical interviews.

Problem Statement

Given two integers A and B, we need to find an integer X such that (X XOR A) is minimum possible and the count of set bits in X is equal to the count of set bits in B.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Example

Input: A=5, B=7

Output: X=7

(5)2 = 101

(7)2 = 111

xor will be minimum when X=7, i.e. (7 xor 5)=2

Method

We need to find the minimum xor of two numbers. The minimum possible value of xor is 0, and it is achieved when two numbers are equal. So X can be equal to A, but in that case, A should have the same number of set bits as B. So, we should try to generate X’s binary representation as close to A as possible.

We will start traversing from the most significant bit in A to the least significant bit, and if a bit is set(i.e., 1) at the current position, then this bit also needs to be set bit in the required number X in order to minimize the value of XOR, but the number of bits set has to be equal to the number of set bits in B and to satisfy this condition, we need to handle three cases.

Case 1

when the count of set bits in the required number X has reached the count of set bits in B, then the rest bits of X will be 0.

Case 2

It is also possible that the count of set bits in B is more than the number of set bits in A. In that case, start filling the unset bits of X to set bits from the least significant bit of X to the most significant bit of X.

Case 3

If the number of set bits is still not equal to B, add the remaining number of set bits to the left of the most significant bit of X to make set bits of X equal to the set bits of B.

Code

// C++ implementation of the above algorithm #include <bits/stdc++.h> usingnamespacestd;

// function to return the value of X such that (X xor A) is minimum // and the number of set bits in X is equal to the number // of set bits in B intminXOR(int A, int B) { int setBits = 0, ans = 0; setBits = __builtin_popcount(B); // number of set bits in B

// creating the binary representation of A in stack s stack<shortint> s; while(A>0) { s.push(A%2); A=A/2; } // decrease the count of setBits as in the required number set bits has to be // equal to the count of set bits in B // Creating the nearest possible number in X in binary form. // Using vector as the number in binary for can be large. vector<shortint> X; // handling case 1 while(!s.empty()) { if(s.top()==1 && setBits>0) { X.push_back(1); setBits--; } else { X.push_back(0); } s.pop(); } // handling case 2 //Filling the unset bits from the least significant bit to the

//most significant bit //if the setBits are not equal to zero for(int i=X.size()-1;i>=0 && setBits>0;i--) { if(X[i]==0) { X[i]=1; setBits--; } } int mask; for(int i=X.size()-1;i>=0;i--) { mask=1<<(X.size()-i-1); ans+=X[i]*mask; } int n=X.size();

// handling case 3

//if the number of setBits is still not equal to zero //adding the remaining number of set bits to the left of the

//most significant bit //to make set bits of X equal to the set bits of B. while(setBits>0) { ans+=1<<n; n++; setBits--; } return ans; } // Driver code intmain() { int A = 5, B = 7; cout <<"value of X = "<<minXOR(A, B); return0; }

Output:

value of X = 7

Complexity analysis

Time complexity: Here, every loop runs at most bits in the binary representation of A or B, i.e., log(N) times. So, it is O(logN).

Space complexity: A stack and a vector are used whose size is nothing but the number of bits in the binary representation of A or X. So, Space complexity is also O(logN).

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.