Skip to content

2429. Minimize XOR 👍

  • Time: $O(\log \texttt{num1} + \log \texttt{num2})$
  • Space: $O(1)$
 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
28
29
30
class Solution {
 public:
  int minimizeXor(unsigned num1, unsigned num2) {
    constexpr int kMaxBit = 30;
    int bits = popcount(num2);
    // Can turn off all the bits in `num1`.
    if (popcount(num1) == bits)
      return num1;

    int ans = 0;

    // Turn off the MSB if we have `bits` quota.
    for (int i = kMaxBit; i >= 0; --i)
      if (num1 >> i & 1) {
        ans |= 1 << i;
        if (--bits == 0)
          return ans;
      }

    // Turn on the LSB if we still have `bits`.
    for (int i = 0; i < kMaxBit; ++i)
      if ((num1 >> i & 1) == 0) {
        ans |= 1 << i;
        if (--bits == 0)
          return ans;
      }

    return ans;
  }
};

 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
28
29
class Solution {
  public int minimizeXor(int num1, int num2) {
    final int kMaxBit = 30;
    int bits = Integer.bitCount(num2);
    // Can turn off all the bits in `num1`.
    if (Integer.bitCount(num1) == bits)
      return num1;

    int ans = 0;

    // Turn off the MSB if we have `bits` quota.
    for (int i = kMaxBit - 1; i >= 0; --i)
      if ((num1 >> i & 1) == 1) {
        ans |= 1 << i;
        if (--bits == 0)
          return ans;
      }

    // Turn on the LSB if we still have `bits`.
    for (int i = 0; i < kMaxBit; ++i)
      if ((num1 >> i & 1) == 0) {
        ans |= 1 << i;
        if (--bits == 0)
          return ans;
      }

    return ans;
  }
}

 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
class Solution:
  def minimizeXor(self, num1: int, num2: int) -> int:
    kMaxBit = 30
    bits = num2.bit_count()
    # Can turn off all the bits in `num1`.
    if num1.bit_count() == bits:
      return num1

    ans = 0

    # Turn off the MSB if we have `bits` quota.
    for i in reversed(range(kMaxBit)):
      if num1 >> i & 1:
        ans |= 1 << i
        bits -= 1
        if bits == 0:
          return ans

    # Turn on the LSB if we still have `bits`.
    for i in range(kMaxBit):
      if (num1 >> i & 1) == 0:
        ans |= 1 << i
        bits -= 1
        if bits == 0:
          return ans

    return ans