# Minimize XOR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-xor)
Canonical: https://scaleengineer.com/dsa/problems/minimize-xor
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## 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.

**Example 1:**

**Input:** num1 = 3, num2 = 5
**Output:** 3
**Explanation:**
The binary representations of num1 and num2 are 0011 and 0101, respectively.
The integer **3** has the same number of set bits as num2, and the value `3 XOR 3 = 0` is minimal.

**Example 2:**

**Input:** num1 = 1, num2 = 12
**Output:** 3
**Explanation:**
The binary representations of num1 and num2 are 0001 and 1100, respectively.
The integer **3** has the same number of set bits as num2, and the value `3 XOR 1 = 2` is minimal.

**Constraints:**

* `1 <= num1, num2 <= 109`

# Approaches
## Greedy Approach with Case Analysis
This approach is based on a greedy strategy that considers three separate cases based on the comparison between the number of set bits in `num1` and `num2`. The goal is to construct `x` by making decisions that minimize `x XOR num1` at each step, tailored to each specific case.
**Time:** O(1), as the loops run a fixed number of times (at most 31, for 32-bit integers), making the runtime constant. · **Space:** O(1), as we only use a few variables to store counts and the result, regardless of the input size.
**Pros:** Logically straightforward, breaking the problem down into understandable sub-problems.; Correct and efficient for the given constraints.
**Cons:** The code is slightly more verbose due to the explicit branching for the three cases.; The logic is split, whereas a more elegant, unified solution exists.
### Explanation
First, we calculate the number of set bits for `num1` and `num2`, let's call them `bits1` and `bits2` respectively. The logic then branches into three distinct scenarios:

1.  **`bits1 == bits2`**: To make `x XOR num1` minimal (i.e., 0), `x` must be equal to `num1`. Since `x` would then have `bits1` set bits, which is equal to the required `bits2`, this is the optimal solution. So, `x = num1`.

2.  **`bits2 > bits1`**: We need `x` to have more set bits than `num1`. To keep `x` as close to `num1` as possible, we start by setting `x = num1`. This ensures all the original set bits of `num1` are matched, minimizing the most significant part of the XOR result. Then, we need to set `bits2 - bits1` additional bits. To cause the smallest increase in the XOR value, we should set these bits at the least significant available positions. We iterate from the least significant bit (LSB) upwards, and for each position `i` where `num1` has a 0, we set the `i`-th bit in `x` until we have set the required number of additional bits.

3.  **`bits2 < bits1`**: We need `x` to have fewer set bits than `num1`. To minimize the XOR result, we must prioritize matching the most significant set bits of `num1`. We construct `x` from scratch (`x=0`). We iterate from the most significant bit (MSB) downwards. If the `i`-th bit is set in `num1`, we set the `i`-th bit in `x` and decrement our count of needed bits. We stop after we have set `bits2` bits in `x`. This ensures `x` is composed of the `bits2` most significant bits of `num1`.

```java
class Solution {
    public int minimizeXor(int num1, int num2) {
        int bits1 = Integer.bitCount(num1);
        int bits2 = Integer.bitCount(num2);
        int x = 0;

        if (bits1 == bits2) {
            return num1;
        } else if (bits2 > bits1) {
            x = num1;
            int diff = bits2 - bits1;
            for (int i = 0; i <= 30 && diff > 0; i++) {
                if ((num1 & (1 << i)) == 0) {
                    x |= (1 << i);
                    diff--;
                }
            }
        } else { // bits2 < bits1
            int count = bits2;
            for (int i = 30; i >= 0 && count > 0; i--) {
                if ((num1 & (1 << i)) != 0) {
                    x |= (1 << i);
                    count--;
                }
            }
        }
        return x;
    }
}
```
### Algorithm
- Calculate `bits1 = Integer.bitCount(num1)` and `bits2 = Integer.bitCount(num2)`.
- **Case 1: `bits1 == bits2`**
  - The optimal `x` is `num1` itself, as `num1 XOR num1 = 0`, which is the minimum possible XOR value. Return `num1`.
- **Case 2: `bits2 > bits1`**
  - To minimize the XOR value, `x` should be as similar to `num1` as possible. Start with `x = num1`.
  - We need to set an additional `diff = bits2 - bits1` bits in `x`.
  - To cause the smallest increase in `x XOR num1`, set these bits at the least significant positions where `num1` has a 0.
  - Iterate from `i = 0` to `30`. If the `i`-th bit of `num1` is 0, set the `i`-th bit in `x` and decrement `diff` until `diff` is 0.
- **Case 3: `bits2 < bits1`**
  - To minimize the XOR value, `x` must match the most significant set bits of `num1`.
  - Initialize `x = 0`.
  - We need to set `bits2` bits in `x`.
  - Iterate from `i = 30` down to `0`. If the `i`-th bit of `num1` is 1, set the `i`-th bit in `x` and decrement a counter for the bits we need to set. Stop when the counter reaches 0.
- Return the constructed `x`.

## Unified Two-Pass Greedy Approach
This is a more refined and elegant greedy approach that solves the problem without explicit case analysis. It uses two passes over the bits of the numbers to construct the optimal `x`. The first pass prioritizes matching the most significant bits of `num1` to minimize the XOR value, and the second pass handles any remaining bits that need to be set.
**Time:** O(1), as the two loops run a fixed number of times (at most 31 each), independent of the input values `num1` and `num2`. · **Space:** O(1), using only a constant amount of extra space for variables.
**Pros:** Highly efficient with constant time and space complexity.; Elegant and concise, handling all cases with a single, unified logic.; Considered the optimal solution for this problem.
**Cons:** The underlying logic might be slightly less intuitive at first glance compared to a direct case-by-case analysis.
### Explanation
The core idea is to build `x` by making the best greedy choice for each bit, starting from the most significant. To minimize `x XOR num1`, we want the bits of `x` to match the bits of `num1` as much as possible, especially at higher-value positions.

First, we determine the target number of set bits for `x`, which is `k = Integer.bitCount(num2)`.

**Pass 1 (MSB to LSB):** We iterate from bit 30 down to 0. For each position `i`, if the `i`-th bit is set in `num1` and we still need to set bits in `x` (i.e., `k > 0`), we set the `i`-th bit in `x`. This action makes the `i`-th bit of `x XOR num1` zero, which is the best possible outcome for this high-value bit. We decrement `k` each time we set a bit. This pass ensures that `x` matches `num1` on its most significant set bits, up to the number of bits we are allowed to set.

**Pass 2 (LSB to MSB):** After the first pass, if `k` is still greater than 0, it means `num2` had more set bits than `num1`. We must set the remaining `k` bits in `x`. To minimize the resulting `x XOR num1` value, we should set these bits in the lowest possible positions where `x` does not have a bit set yet. We iterate from bit 0 up to 30. For each position `i`, if the `i`-th bit of `x` is 0 and `k > 0`, we set the `i`-th bit in `x` and decrement `k`.

This two-pass process correctly constructs the unique integer `x` that satisfies both conditions, regardless of whether `num1` has more, fewer, or the same number of set bits as the target.

```java
class Solution {
    public int minimizeXor(int num1, int num2) {
        int setBitsToPlace = Integer.bitCount(num2);
        int x = 0;

        // Pass 1: Prioritize matching the most significant set bits of num1.
        // This minimizes the XOR value by making the most significant bits of the result 0.
        for (int i = 30; i >= 0 && setBitsToPlace > 0; i--) {
            if ((num1 & (1 << i)) != 0) {
                x |= (1 << i);
                setBitsToPlace--;
            }
        }

        // Pass 2: If more bits need to be set, fill them in from the least significant
        // available positions. This adds the smallest possible value to the XOR result.
        for (int i = 0; i <= 30 && setBitsToPlace > 0; i++) {
            // Check if the bit is not already set in x
            if ((x & (1 << i)) == 0) {
                x |= (1 << i);
                setBitsToPlace--;
            }
        }

        return x;
    }
}
```
### Algorithm
- Calculate `k = Integer.bitCount(num2)`, which is the target number of set bits for `x`.
- Initialize the result `x = 0`.
- **Pass 1 (MSB to LSB):** Iterate `i` from 30 down to 0.
  - If the `i`-th bit of `num1` is 1 and we still need to set bits (`k > 0`):
    - Set the `i`-th bit of `x` (i.e., `x |= (1 << i)`).
    - Decrement `k`.
- **Pass 2 (LSB to MSB):** If `k` is still greater than 0 after the first pass:
  - Iterate `i` from 0 up to 30.
  - If the `i`-th bit of `x` is 0 and `k > 0`:
    - Set the `i`-th bit of `x`.
    - Decrement `k`.
- Return the final constructed `x`.

# Solutions
### Java

```java
class Solution {
public
  int minimizeXor(int num1, int num2) {
    int cnt = Integer.bitCount(num2);
    int x = 0;
    for (int i = 30; i >= 0 && cnt > 0; --i) {
      if ((num1 >> i & 1) == 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    for (int i = 0; cnt > 0; ++i) {
      if ((num1 >> i & 1) == 0) {
        x |= 1 << i;
        --cnt;
      }
    }
    return x;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeXor(int num1, int num2) {
    int cnt = __builtin_popcount(num2);
    int x = 0;
    for (int i = 30; ~i && cnt; --i) {
      if (num1 >> i & 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    for (int i = 0; cnt; ++i) {
      if (num1 >> i & 1 ^ 1) {
        x |= 1 << i;
        --cnt;
      }
    }
    return x;
  }
};

```

### Python

```python
class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int: cnt = num2 . bit_count() x = 0 for i in range(30, - 1, - 1): if num1 >> i & 1 and cnt: x |= 1 << i cnt -= 1 for i in range(30): if num1 >> i & 1 ^ 1 and cnt: x |= 1 << i cnt -= 1 return x

```