Skip to content

4047. Minimum Operations to Make XOR of All Elements Zero πŸ”’

DifficultyHard

Description

You are given an integer array nums consisting of positive integers.

You may perform the following operation any number of times:

  • Choose two distinct indices i and j such that nums[i] != nums[j], and replace either nums[i] or nums[j] with nums[i] ^ nums[j], where ^ denotes the bitwise XOR.

Return the minimum number of operations required to make the bitwise XOR of all elements in nums equal to 0. If it is impossible, return -1.

 

Example 1:

Input: nums = [8,1,4,8,2]

Output: 3

Explanation:

One optimal sequence of operations is:

  • Choose indices 0 and 1, and replace nums[0] with 8 ^ 1 = 9. The array becomes [9, 1, 4, 8, 2].
  • Choose indices 2 and 3, and replace nums[3] with 4 ^ 8 = 12. The array becomes [9, 1, 4, 12, 2].
  • Choose indices 0 and 4, and replace nums[0] with 9 ^ 2 = 11. The array becomes [11, 1, 4, 12, 2].

The XOR of all elements of nums is 11 ^ 1 ^ 4 ^ 12 ^ 2 = 0, so the answer is 3.

Example 2:

Input: nums = [1,2,3]

Output: 0

Explanation:

The XOR of all elements of nums is 1 ^ 2 ^ 3 = 0, so no operations are required.

Example 3:

Input: nums = [1,2,4]

Output: -1

Explanation:

It is impossible to make the XOR of all elements of nums equal to 0, so the answer is -1.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 2000

Solutions

Solution 1

1


1


1


1

Comments