15.01.2025
2429. Minimize XOR medium blog post substack youtube deep-dive
Join me on Telegram
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 inres
)
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;
}