Skip to content

2429. Minimize XOR

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:

  • 1 <= num1, num2 <= 109

Solutions

Solution 1: Greedy + Bit Manipulation

Thinking

\(x\) must have the same popcount as \(num2\) and minimize \(x\oplus num1\), so \(x\) should reuse \(num1\)'s high \(1\)-bits. At most \(31\) bits, greedy by position works.

First take \(num1\)'s \(1\)-bits from high to low; if slots remain, fill \(num1\)'s \(0\)-bits from low to high so the XOR does not grow in high bits.

According to the problem description, we first calculate the number of set bits in \(\textit{num2}\), denoted as \(\textit{cnt}\). Then, we iterate from the highest to the lowest bit of \(\textit{num1}\); if the current bit is \(1\), we set the corresponding bit in \(x\) to \(1\) and decrement \(\textit{cnt}\), until \(\textit{cnt}\) becomes \(0\). If \(\textit{cnt}\) is still not \(0\), we iterate from the lowest bit upwards, setting positions where \(\textit{num1}\) has \(0\) to \(1\) in \(x\), and decrement \(\textit{cnt}\) until it reaches \(0\).

The time complexity is \(O(\log n)\), where \(n\) is the maximum value of \(\textit{num1}\) and \(\textit{num2}\). The space complexity is \(O(1)\).

 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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn minimize_xor(num1: i32, mut num2: i32) -> i32 {
        let mut cnt = 0;
        while num2 > 0 {
            num2 -= num2 & -num2;
            cnt += 1;
        }
        let mut x = 0;
        let mut c = cnt;
        for i in (0..=30).rev() {
            if c > 0 && (num1 >> i) & 1 == 1 {
                x |= 1 << i;
                c -= 1;
            }
        }
        for i in 0..=30 {
            if c == 0 {
                break;
            }
            if ((num1 >> i) & 1) == 0 {
                x |= 1 << i;
                c -= 1;
            }
        }
        x
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int MinimizeXor(int num1, int num2) {
        int cnt = BitOperations.PopCount((uint)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;
    }
}

Comments