Sponsored
Sponsored
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.
Solve with full IDE support and test cases
JavaScript uses similar logic by looping over the array and calculating the XOR difference with k to count necessary bit flips.
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#include <stdio.h>
2
3int countSetBits(int n) {
4 int count = 0;
5 while (n) {
6 count += n & 1;
7 n >>= 1;
8 }
9 return count;
10}
11
12int minOperations(int* nums, int numsSize, int k) {
13 int xor_sum = 0;
14 for (int i = 0; i < numsSize; i++) {
15 xor_sum ^= nums[i];
16 }
17 int set_bits_xor = countSetBits(xor_sum);
18 int set_bits_k = countSetBits(k);
19 return abs(set_bits_xor - set_bits_k);
20}
21
22int main() {
23 int nums[] = {2, 1, 3, 4};
24 int k = 1;
25 printf("%d\n", minOperations(nums, 4, k));
26 return 0;
27}
28We define a helper function to count the set bits of a number. We calculate XOR sum first, and then find the difference in set bit numbers compared to k.