Sponsored
Sponsored
Solve with full IDE support and test cases
This approach involves using bit manipulation to find out which bits are different between the XOR of the array and k. For each differing bit, calculate the minimum number of flips needed across all elements to switch that bit in the resultant XOR.
Time Complexity: O(n), where n is the length of the array, since we only traverse it twice.
Space Complexity: O(1), as no additional data structures are used.
1#include <stdio.h>
2
3int minOperations(int* nums, int numsSize, int k) {
4 int xor_sum = 0;
5 for (int i = 0; i < numsSize; i++) {
6 xor_sum ^= nums[i];
7 }
8 int diff = xor_sum ^ k;
9 int operations = 0;
10 while (diff != 0) {
11 operations += diff & 1;
12 diff >>= 1;
13 }
14 return operations;
15}
16
17int main() {
18 int nums[] = {2, 1, 3, 4};
19 int k = 1;
20 printf("%d\n", minOperations(nums, 4, k));
21 return 0;
22}
23We start by calculating the XOR sum of the array, XOR it with k to find the differing bits, and count each differing bit as an operation needed to make the elements' XOR equal to k.
In this approach, the focus is on counting the set bits of two numbers (XOR sum and k) - i.e., how many bits are 1 in their binary representation. We aim to equalize the set bits count by flipping specific bits in nums.
Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).
1
class Solution {
public int CountSetBits(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public int MinOperations(int[] nums, int k) {
int xorSum = 0;
foreach (int num in nums) {
xorSum ^= num;
}
int setBitsXor = CountSetBits(xorSum);
int setBitsK = CountSetBits(k);
return Math.Abs(setBitsXor - setBitsK);
}
static void Main(string[] args) {
int[] nums = { 2, 1, 3, 4 };
int k = 1;
Solution solution = new Solution();
Console.WriteLine(solution.MinOperations(nums, k));
}
}This C# code counts the number of set bits in both the XOR sum and k, and uses the difference to determine the minimum number of flips needed.