## Leetcode 2429 – Minimize XOR

Source: https://leetcode.com/problems/minimize-xor/

## Problem statement

Given two positive integers `num1`

and `num2`

, find the 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 = 5Output:3Explanation:The binary representations of num1 and num2 are 0011 and 0101, respectively. The integer3has the same number of set bits as num2, and the value`3 XOR 3 = 0`

is minimal.

**Example 2:**

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

is minimal.

**Constraints:**

`1 <= num1, num2 <= 10`

^{9}

## Solution

This is a very nice binary arithmetic problem to sharpen the implementation skills.

The intuition is that we want to use as many of the bits as possible to “turn off” the most significant bits of the initial number by coinciding them with the set bits of *num1* (since 1 ^ 1 = 0). If there are any remaining bits to place, the approach would be to use them to set the low significant bits by coinciding them with zeroes in *num1* (since 1 ^ 0 = 1).

So, we can generate the optimal solution iteratively by performing following steps:

- Count the number of bits in
*num2* - Clear the set bits from the left to the right in
*num1*(to reduce the resulting number as much as possible towards zero) - Place remaining bits in the free positions from the right to the left (to keep the number as small as possible)

Final result is stored in the variable *r*, which is set to zero at the start and whose bits are set one by one as we’re constructing the solution.

Apparently, C++ implementation bellow resulted in a VERY fast and memory efficient solution:

class Solution { public: int minimizeXor(int num1, int num2) { int c = 0, r = 0; // count the set bits in num2 while (num2) { c += (num2 & 1); num2 >>= 1; } // clear bits from left to right in num1 int b = (1 << 30); // start from the right while (b) { if (b & num1) { num1 ^= b; // clear the current bit r |= b; // set the bit in the solution c--; if (c == 0) break; } b >>= 1; // move the bit to the right } // add the remaining bits from right to left b = 1; while (c) { if (!(r & b)) { // if the current position is free... r |= b; // ... set it c--; } b <<= 1; } return r; } };