« back

Minimum X (xor) A

Tags : geeksforgeeks, array, cpp, medium

Problem Statement - link #

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

Your Task:

You don’t need to read input or print anything. Your task is to complete the function minVal() that takes integer A and B as input and returns the value of X according to the question.

Expected Time Complexity: O(log MAX(A,B))
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Input: 
A = 7, B = 12
Output: 6
Explanation:
(7)2= 111
(12)2= 1100
The XOR will be minimum when x = 6 
i.e. (6 XOR 7) = 1 and the number 
of set bits in 6 is equal to the 
number of set bits in 12.

Example 2:

Input: 
A = 3, B = 5
Output: 3
Explanation:
Binary(A) = Binary(3) = 011
Binary(B) = Binary(5) = 101
The XOR will be minimum when x = 3
i.e. (3 XOR 3) = 0 and the number
of set bits in 3 is equal
to the number of set bits in 5.

Constraints #

Solutions #


class Solution {
  public:
    int minVal(int a, int b) {
        // code here
        int bSB = __builtin_popcount(b);
        int x = a;
        int xSB = __builtin_popcount(x);
        int diff = abs(bSB-xSB);
        if(diff==0) {
            return x;
        }
        else if(bSB<xSB) {
            while(diff>0) {
                x &= (x-1);
                diff--;
            }
        }
        else {
            while(diff>0) {
                x |= (x+1);
                diff--;
            }
        }
        return x;
    }
};