##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2429.html

# 2429. Minimize XOR

• Difficulty: Medium.
• Related Topics: .
• Similar Questions: Maximum XOR of Two Numbers in an Array, Maximum XOR With an Element From Array.

## Problem

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 = 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 <= 10^9

## Solution (Java, C++, Python)

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

• class Solution {
public:
int minimizeXor(int num1, int num2) {
int cnt = __builtin_popcount(num2);
int ans = 0;
for (int i = 30; i >= 0; --i) {
if ((num1 >> i) & 1) {
ans |= 1 << i;
if (--cnt == 0) {
return ans;
}
}
}
for (int i = 0; i < 31; ++i) {
if (((num1 >> i) & 1) == 0) {
ans |= 1 << i;
if (--cnt == 0) {
return ans;
}
}
}
return 0;
}
};

• class Solution:
def minimizeXor(self, num1: int, num2: int) -> int:
cnt = num2.bit_count()
ans = 0
for i in range(30, -1, -1):
if (num1 >> i) & 1:
ans |= 1 << i
cnt -= 1
if cnt == 0:
return ans
for i in range(31):
if (num1 >> i) & 1 == 0:
ans |= 1 << i
cnt -= 1
if cnt == 0:
return ans
return 0


• func minimizeXor(num1 int, num2 int) int {
cnt := bits.OnesCount(uint(num2))
ans := 0
for i := 30; i >= 0; i-- {
if num1>>i&1 == 1 {
ans |= 1 << i
cnt--
if cnt == 0 {
return ans
}
}
}
for i := 0; i < 31; i++ {
if num1>>i&1 == 0 {
ans |= 1 << i
cnt--
if cnt == 0 {
return ans
}
}
}
return 0
}

• function minimizeXor(num1: number, num2: number): number {
let ans = num1;
let target = num1
.toString(2)
.split('')
.reduce((a, c) => a + Number(c), 0);
let count = num2
.toString(2)
.split('')
.reduce((a, c) => a + Number(c), 0);
while (count > target) {
ans |= ans + 1;
count -= 1;
}
while (count < target) {
ans &= ans - 1;
count += 1;
}
return ans;
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).