4047. 使所有元素的异或为零所需的最小操作次数 🔒
难度困难
题目描述
给你一个由 正整数 组成的整数数组 nums。
你可以执行以下 操作 任意次：
- 选择两个 不同的 下标
i和j，满足nums[i] != nums[j]，并将nums[i]或nums[j]中的一个替换为nums[i] ^ nums[j]，其中^表示 按位异或。
返回使 nums 中所有元素的 按位异或 结果等于 0 所需的 最少 操作次数。如果无法做到，返回 -1。
示例 1：
输入： nums = [8,1,4,8,2]
输出： 3
解释：
一种最优的操作序列如下：
- 选择下标 0 和 1，并将
nums[0]替换为8 ^ 1 = 9。数组变为[9, 1, 4, 8, 2]。 - 选择下标 2 和 3，并将
nums[3]替换为4 ^ 8 = 12。数组变为[9, 1, 4, 12, 2]。 - 选择下标 0 和 4，并将
nums[0]替换为9 ^ 2 = 11。数组变为[11, 1, 4, 12, 2]。
nums 中所有元素的异或结果为 11 ^ 1 ^ 4 ^ 12 ^ 2 = 0，因此答案为 3。
示例 2：
输入： nums = [1,2,3]
输出： 0
解释：
nums 中所有元素的异或结果为 1 ^ 2 ^ 3 = 0，因此不需要执行任何操作。
示例 3：
输入： nums = [1,2,4]
输出： -1
解释：
无法使 nums 中所有元素的异或结果等于 0，因此答案为 -1。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 2000
解法
方法一
1 | |
1 | |
1 | |
1 | |