Question

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

中文文档

Description

You are given a 0-indexed integer array nums and a positive integer k.

You can apply the following operation on the array any number of times:

• Choose any element of the array and flip a bit in its binary representation. Flipping a bit means changing a 0 to 1 or vice versa.

Return _the minimum number of operations required to make the bitwise _XOR_ of all elements of the final array equal to _k.

Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.

 

Example 1:

Input: nums = [2,1,3,4], k = 1
Output: 2
Explanation: We can do the following operations:
- Choose element 2 which is 3 == (011)2, we flip the first bit and we obtain (010)2 == 2. nums becomes [2,1,2,4].
- Choose element 0 which is 2 == (010)2, we flip the third bit and we obtain (110)2 = 6. nums becomes [6,1,2,4].
The XOR of elements of the final array is (6 XOR 1 XOR 2 XOR 4) == 1 == k.
It can be shown that we cannot make the XOR equal to k in less than 2 operations.

Example 2:

Input: nums = [2,0,2,0], k = 0
Output: 0
Explanation: The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 106
• 0 <= k <= 106

Solutions

Solution 1: Bit Manipulation

We can perform a bitwise XOR operation on all elements in the array $nums$. The number of bits that differ from the binary representation of $k$ in the result is the minimum number of operations.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def minOperations(self, nums: List[int], k: int) -> int:
    return reduce(xor, nums, k).bit_count()

class Solution {
  public int minOperations(int[] nums, int k) {
    for (int x : nums) {
      k ^= x;
    }
    return Integer.bitCount(k);
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums, int k) {
    for (int x : nums) {
      k ^= x;
    }
    return __builtin_popcount(k);
  }
};

func minOperations(nums []int, k int) (ans int) {
  for _, x := range nums {
    k ^= x
  }
  return bits.OnesCount(uint(k))
}

function minOperations(nums: number[], k: number): number {
  for (const x of nums) {
    k ^= x;
  }
  return bitCount(k);
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}