Description#
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:
Solutions#
Solution 1: Greedy + Bit Manipulation#
According to the problem description, we first calculate the number of set bits $cnt$ in $num2$, then enumerate each bit of $num1$ from high to low. If the bit is $1$, we set the corresponding bit in $x$ to $1$ and decrement $cnt$ by $1$, until $cnt$ is $0$. If $cnt$ is still not $0$ at this point, we start from the low bit and set each bit of $num1$ that is $0$ to $1$, and decrement $cnt$ by $1$, until $cnt$ is $0$.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the maximum value of $num1$ and $num2$.
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func minimizeXor(num1 int, num2 int) int {
cnt := bits.OnesCount(uint(num2))
x := 0
for i := 30; i >= 0 && cnt > 0; i-- {
if num1>>i&1 == 1 {
x |= 1 << i
cnt--
}
}
for i := 0; cnt > 0; i++ {
if num1>>i&1 == 0 {
x |= 1 << i
cnt--
}
}
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function minimizeXor(num1: number, num2: number): number {
let cnt = 0;
while (num2) {
num2 &= num2 - 1;
++cnt;
}
let x = 0;
for (let i = 30; i >= 0 && cnt > 0; --i) {
if ((num1 >> i) & 1) {
x |= 1 << i;
--cnt;
}
}
for (let i = 0; cnt > 0; ++i) {
if (!((num1 >> i) & 1)) {
x |= 1 << i;
--cnt;
}
}
return x;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def minimizeXor(self, num1: int, num2: int) -> int:
cnt1 = num1.bit_count()
cnt2 = num2.bit_count()
while cnt1 > cnt2:
num1 &= num1 - 1
cnt1 -= 1
while cnt1 < cnt2:
num1 |= num1 + 1
cnt1 += 1
return num1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int minimizeXor(int num1, int num2) {
int cnt1 = Integer.bitCount(num1);
int cnt2 = Integer.bitCount(num2);
for (; cnt1 > cnt2; --cnt1) {
num1 &= (num1 - 1);
}
for (; cnt1 < cnt2; ++cnt1) {
num1 |= (num1 + 1);
}
return num1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int minimizeXor(int num1, int num2) {
int cnt1 = __builtin_popcount(num1);
int cnt2 = __builtin_popcount(num2);
for (; cnt1 > cnt2; --cnt1) {
num1 &= (num1 - 1);
}
for (; cnt1 < cnt2; ++cnt1) {
num1 |= (num1 + 1);
}
return num1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
| func minimizeXor(num1 int, num2 int) int {
cnt1 := bits.OnesCount(uint(num1))
cnt2 := bits.OnesCount(uint(num2))
for ; cnt1 > cnt2; cnt1-- {
num1 &= (num1 - 1)
}
for ; cnt1 < cnt2; cnt1++ {
num1 |= (num1 + 1)
}
return num1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function minimizeXor(num1: number, num2: number): number {
let cnt1 = bitCount(num1);
let cnt2 = bitCount(num2);
for (; cnt1 > cnt2; --cnt1) {
num1 &= num1 - 1;
}
for (; cnt1 < cnt2; ++cnt1) {
num1 |= num1 + 1;
}
return num1;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
|
