Minimize XOR - Practice Coding Problems

Minimize XOR - Problem

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

Input & Output

Example 1 — Perfect Match

$ Input: num1 = 3, num2 = 5

› Output: 3

💡 Note: num1 = 3 (binary: 011) has 2 set bits. num2 = 5 (binary: 101) has 2 set bits. Since 3 already has the required number of bits, x = 3 gives XOR = 0, which is minimal.

Example 2 — Need More Bits

$ Input: num1 = 1, num2 = 12

› Output: 3

💡 Note: num1 = 1 (binary: 001) has 1 set bit. num2 = 12 (binary: 1100) has 2 set bits. We need x with 2 set bits. Starting from 1, we add the lowest bit to get 3 (binary: 011). XOR: 3 ⊕ 1 = 2.

Example 3 — Need Fewer Bits

$ Input: num1 = 25, num2 = 6

› Output: 17

💡 Note: num1 = 25 (binary: 11001) has 3 set bits. num2 = 6 (binary: 110) has 2 set bits. We need x with 2 set bits. Remove the highest bit from 25 to get 17 (binary: 10001) with 2 set bits.

Constraints

1 ≤ num1, num2 ≤ 10⁹
num1 and num2 are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Analyze bit patterns of num1 and num2

Bit Optimization

Construct x to minimize XOR

Result

x with required bits and minimal XOR

Key Takeaway

🎯 Key Insight: Start with num1 and greedily adjust bit count to minimize XOR while maintaining the required number of set bits

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to minimize XOR by making x as similar to num1 as possible while maintaining the exact number of set bits from num2. The greedy approach starts with num1 and optimally adjusts the bit count. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Bit Manipulation	O(log n)	O(1)	Greedily set bits to minimize XOR by copying beneficial bits from num1
Brute Force	O(2^n)	O(1)	Try all possible integers with the required number of set bits

Greedy Bit Manipulation — Algorithm Steps

Count set bits needed from num2
Copy beneficial 1-bits from num1 to x
If more bits needed, set lowest remaining bits
If fewer bits needed, clear highest bits optimally

Visualization

Tap to expand

Step-by-Step Walkthrough

Copy Base

Start with num1 as foundation

Adjust Bits

Add/remove bits optimally

Minimize XOR

Result has minimal XOR

Code -

solution.c — C

#include <stdio.h>

int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int solution(int num1, int num2) {
    int targetBits = countBits(num2);
    
    // Start by copying num1
    int x = num1;
    int currentBits = countBits(x);
    
    if (currentBits == targetBits) {
        return x;
    } else if (currentBits < targetBits) {
        // Need to add more 1-bits at lowest positions
        int need = targetBits - currentBits;
        int bit = 0;
        while (need > 0) {
            if (!(x & (1 << bit))) {
                x |= (1 << bit);
                need--;
            }
            bit++;
        }
    } else {
        // Need to remove some 1-bits from highest positions
        int excess = currentBits - targetBits;
        int bit = 30; // Start from high bits
        while (excess > 0 && bit >= 0) {
            if (x & (1 << bit)) {
                x &= ~(1 << bit);
                excess--;
            }
            bit--;
        }
    }
    
    return x;
}

int main() {
    int num1, num2;
    scanf("%d %d", &num1, &num2);
    
    printf("%d\n", solution(num1, num2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Process each bit position once up to the highest bit

⚡ Linearithmic

Space Complexity

O(1)

Only use constant extra variables for counting and result

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler