LeetCode Entry

2997. Minimum Number of Operations to Make Array XOR Equal to K

29.04.2024 medium 2024 kotlin rust

Bit diff between k and nums xor manipulation

2997. Minimum Number of Operations to Make Array XOR Equal to K medium blog post substack youtube 2024-04-29_07-41.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/587

Problem TLDR

Bit diff between k and nums xor #medium #bit_manipulation

Intuition

Let’s observe how the result xor built:

    // 2  010 -> 110
    // 1  001
    // 3  011 -> 010
    // 4  100
    // x  100 -> 000 -> 001
    // k  001

The result x differs from k by two bit flips: 100 -> 000 -> 001. We can do those bit flips on any number in the array, the final xor does not depend on the number choice.

Approach

Let’s try to use built-in methods: fold, countOneBits, count_ones.

Complexity

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

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

Code


    fun minOperations(nums: IntArray, k: Int) =
        nums.fold(k) { r, t -> r xor t }.countOneBits()



    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        nums.iter().fold(k, |r, t| r ^ t).count_ones() as _
    }