LeetCode Entry

2429. Minimize XOR

15.01.2025 medium 2025 kotlin rust

Min xor with num1, bits count of num2

2429. Minimize XOR medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/865

Problem TLDR

Min xor with num1, bits count of num2 #medium

Intuition


    // 0011
    // 0101

    // 0101
    //  1 1

    // 11001
    // 1001000
  • if bits count are equal, just return num1, as num1 ^ num1 = 0
  • if bits count is more, bc(num1) > bc(num2), we want all the bits of num1 plus the lowest possible vacancies filled
  • otherwise, we want lowest possible bits of num1 turned off to make res ^ num1 minimum (so, leave highest bits of num1 set in res)

Approach

  • we can iterate over bits, or over counts differences
  • careful of the Rust usize overflow

Complexity

  • Time complexity: \(O(log(n))\)

  • Space complexity: \(O(1)\)

Code


    fun minimizeXor(num1: Int, num2: Int): Int {
        var cnt = num2.countOneBits() - num1.countOneBits()
        var res = num1; var b = 0
        while (cnt != 0) {
            while ((num1 and (1 shl b) > 0) == cnt > 0) b++
            res = res xor (1 shl b++)
            if (cnt > 0) cnt-- else cnt++
        }
        return res
    }



    pub fn minimize_xor(num1: i32, num2: i32) -> i32 {
        let (mut cnt, mut r) =
          ((num2.count_ones() - num1.count_ones()) as i8, num1);
        for b in 0..32 {
            if cnt != 0 && ((num1 & (1 << b)) > 0) != (cnt > 0) {
                r ^= 1 << b; if cnt > 0 { cnt -= 1 } else { cnt += 1 }
            }
        }; r
    }



    int minimizeXor(int num1, int num2) {
        int cnt = __builtin_popcount(num2) - __builtin_popcount(num1), r = num1;
        for (int b = 0; b < 32 && cnt; ++b)
            if ((num1 & (1 << b)) > 0 != cnt > 0)
                r ^= 1 << b, cnt -= 2 * (cnt > 0) - 1;
        return r;
    }