深圳企业网站制作推广运营,网络舆情监测预警系统,兰州移动官网网站建设,坊网站建设给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
你可以对数组执行以下操作 任意次 #xff1a;
选择数组里的 任意 一个元素#xff0c;并将它的 二进制 表示 翻转 一个数位#xff0c;翻转数位表示将 0 变成 1 或者将 1 变成 0 。 你的目标是让数组里 所有 元素…给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
你可以对数组执行以下操作 任意次
选择数组里的 任意 一个元素并将它的 二进制 表示 翻转 一个数位翻转数位表示将 0 变成 1 或者将 1 变成 0 。 你的目标是让数组里 所有 元素的按位异或和得到 k 请你返回达成这一目标的 最少 操作次数。
注意你也可以将一个数的前导 0 翻转。比方说数字 (101)2 翻转第四个数位得到 (1101)2 。
示例 1
输入nums [2,1,3,4], k 1 输出2 解释我们可以执行以下操作
选择下标为 2 的元素也就是 3 (011)2 我们翻转第一个数位得到 (010)2 2 。数组变为 [2,1,2,4] 。选择下标为 0 的元素也就是 2 (010)2 我们翻转第三个数位得到 (110)2 6 。数组变为 [6,1,2,4] 。 最终数组的所有元素异或和为 (6 XOR 1 XOR 2 XOR 4) 1 k 。 无法用少于 2 次操作得到异或和等于 k 。 示例 2
输入nums [2,0,2,0], k 0 输出0 解释数组所有元素的异或和为 (2 XOR 0 XOR 2 XOR 0) 0 k 。所以不需要进行任何操作。
提示
1 nums.length 105 0 nums[i] 106 0 k 106
先求出数组中所有数字的异或和然后看看与k差几位即可
class Solution {
public:int minOperations(vectorint nums, int k) {int xorRes 0;for (int num : nums){xorRes ^ num;}int diff xorRes ^ k;int ans 0;while (diff){ans;diff diff (diff - 1);}return ans;}
};如果nums的长度为n则此算法时间复杂度为O(n)空间复杂度为O(1)。
