Minimum Number of Operations to Make Array XOR Equal to K solution and explanation
9 more videos on this problem
Minimum Number of Operations to Make Array XOR Equal to K | Easy | Leetcode 2997 | codestorywithMIKcodestorywithMIK · 11:09 · 7K views
2997. Minimum Number of Operations to Make Array XOR Equal to K | Bit Manipulation | XOR TricksAryan Mittal · 12:18 · 5K views
2997. Minimum Number of Operations to Make Array XOR Equal to K | leetcode daily challenge | DSAShashCode · 14:37 · 1K views
Leetcode 2997: Minimum Number of Operations to Make Array XOR Equal to K | Biweekly ContestAlgorithms Casts · 9:46 · 594 views
2997. Minimum Number of Operations to Make Array XOR Equal to K (Leetcode Medium)Programming Live with Larry · 5:54 · 511 views
LeetCode 2997 - Minimum Number of Operations to Make Array XOR Equal to K - JavaAlpha-Code · 16:28 · 139 views
Minimum Number of Operations to Make Array XOR Equal to K | 2997Web Mickey · 8:51 · 138 views
Leetcode 2997 || Minimum Number of Operations to Make Array XOR Equal to K || Biweekly ContestKomal Pal · 9:47 · 82 views
Minimum Number of Operations to Make Array XOR Equal to K -Leetcode 2997|| Medium|| Bit ManipulationLevel up with Coding · 9:41 · 45 views
Leetcode 2997 - Minimum Number of Operations to Make Array XOR Equal to KCodeLifey · 8:47 · 44 views
The problem
You are given a 0-indexed integer array nums and a positive integer k.
You can apply the following operation on the array any number of times:
- Choose any element of the array and flip a bit in its binary representation. Flipping a bit means changing a
0to1or vice versa.
Return the minimum number of operations required to make the bitwise XOR of all elements of the final array equal to k.
Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.
Example 1:
Input: nums = [2,1,3,4], k = 1 Output: 2 Explanation: We can do the following operations: - Choose element 2 which is 3 == (011)2, we flip the first bit and we obtain (010)2 == 2. nums becomes [2,1,2,4]. - Choose element 0 which is 2 == (010)2, we flip the third bit and we obtain (110)2 = 6. nums becomes [6,1,2,4]. The XOR of elements of the final array is (6 XOR 1 XOR 2 XOR 4) == 1 == k. It can be shown that we cannot make the XOR equal to k in less than 2 operations.
Example 2:
Input: nums = [2,0,2,0], k = 0 Output: 0 Explanation: The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1060 <= k <= 106
Approach overview
Problem Overview: You’re given an integer array nums and a target value k. In one operation, you can flip any single bit of any element. The goal is to make the XOR of the entire array equal to k using the minimum number of operations.
Approach 1: Bit Manipulation (O(n) time, O(1) space)
Start by computing the XOR of all elements in the array. Call this value currentXor. If the final XOR must be k, then the difference between the two values is diff = currentXor ^ k. Every set bit in diff represents a bit position that must be flipped somewhere in the array.
Because flipping a single bit in any number toggles that bit in the overall XOR, each mismatched bit requires exactly one operation. Iterate through the bits of diff and count how many are set. That count is the minimum number of operations needed. This approach relies on core properties of bit manipulation and the XOR operator.
Approach 2: Count Set Bits (O(n) time, O(1) space)
This approach focuses directly on counting the mismatched bits after computing the array XOR. First iterate through the array and compute currentXor. Then calculate diff = currentXor ^ k. The number of required operations is simply the number of set bits in diff.
You can count these bits using built‑in popcount functions or classic techniques like repeatedly clearing the lowest set bit (diff &= diff - 1). Each set bit corresponds to one required flip operation. Since the integer size is fixed (typically 32 bits), the counting step is effectively constant time.
Recommended for interviews: The expected solution is the XOR difference + set bit count approach. Interviewers want to see that you understand how XOR aggregates bits across an array and how flipping one bit affects the final result. A brute-force bit-by-bit reasoning demonstrates understanding, but the optimized bit manipulation insight shows strong familiarity with XOR properties.
Approach 1: Approach 1: Bit Manipulation
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.
def minOperations(nums, k):
xor_sum = 0
for num in nums:
xor_sum ^= num
diff = xor_sum ^ k
operations = 0
while diff != 0:
operations += diff & 1
diff >>= 1
return operations
# Example usage
nums = [2, 1, 3, 4]
k = 1
print(minOperations(nums, k))public class Solution {
public int minOperations(int[] nums, int k) {
int xorSum = 0;
for (int num : nums) {
xorSum ^= num;
}
int diff = xorSum ^ k;
int operations = 0;
while (diff != 0) {
operations += diff & 1;
diff >>= 1;
}
return operations;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 1, 3, 4};
System.out.println(solution.minOperations(nums, 1));
}
}#include <iostream>
#include <vector>
int minOperations(std::vector<int>& nums, int k) {
int xor_sum = 0;
for (int num : nums) {
xor_sum ^= num;
}
int diff = xor_sum ^ k;
int operations = 0;
while (diff != 0) {
operations += diff & 1;
diff >>= 1;
}
return operations;
}
int main() {
std::vector<int> nums = {2, 1, 3, 4};
int k = 1;
std::cout << minOperations(nums, k) << std::endl;
return 0;
}function minOperations(nums, k) {
let xorSum = 0;
nums.forEach(num => {
xorSum ^= num;
});
let diff = xorSum ^ k;
let operations = 0;
while (diff !== 0) {
operations += diff & 1;
diff >>= 1;
}
return operations;
}
const nums = [2, 1, 3, 4];
const k = 1;
console.log(minOperations(nums, k));#include <stdio.h>
int minOperations(int* nums, int numsSize, int k) {
int xor_sum = 0;
for (int i = 0; i < numsSize; i++) {
xor_sum ^= nums[i];
}
int diff = xor_sum ^ k;
int operations = 0;
while (diff != 0) {
operations += diff & 1;
diff >>= 1;
}
return operations;
}
int main() {
int nums[] = {2, 1, 3, 4};
int k = 1;
printf("%d\n", minOperations(nums, 4, k));
return 0;
}using System;
class Solution {
public int MinOperations(int[] nums, int k) {
int xorSum = 0;
for (int i = 0; i < nums.Length; i++) {
xorSum ^= nums[i];
}
int diff = xorSum ^ k;
int operations = 0;
while (diff != 0) {
operations += diff & 1;
diff >>= 1;
}
return operations;
}
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 Python solution follows the same logic. We compute the XOR of the array and then XOR it with k to find the number of different bits.
Time Complexity: O(n)
Space Complexity: O(1).
Approach 2: Approach 2: Count Set Bits
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.
def countSetBits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def minOperations(nums, k):
xor_sum = 0
for num in nums:
xor_sum ^= num
set_bits_xor = countSetBits(xor_sum)
set_bits_k = countSetBits(k)
return abs(set_bits_xor - set_bits_k)
# Example usage
nums = [2, 1, 3, 4]
k = 1
print(minOperations(nums, k))public 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;
for (int num : nums) {
xorSum ^= num;
}
int setBitsXor = countSetBits(xorSum);
int setBitsK = countSetBits(k);
return Math.abs(setBitsXor - setBitsK);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 1, 3, 4};
System.out.println(solution.minOperations(nums, 1));
}
}#include <iostream>
#include <vector>
#include <cmath>
int countSetBits(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int minOperations(std::vector<int>& nums, int k) {
int xor_sum = 0;
for (int num : nums) {
xor_sum ^= num;
}
int set_bits_xor = countSetBits(xor_sum);
int set_bits_k = countSetBits(k);
return std::abs(set_bits_xor - set_bits_k);
}
int main() {
std::vector<int> nums = {2, 1, 3, 4};
int k = 1;
std::cout << minOperations(nums, k) << std::endl;
return 0;
}function countSetBits(n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>= 1;
}
return count;
}
function minOperations(nums, k) {
let xorSum = 0;
nums.forEach(num => {
xorSum ^= num;
});
let setBitsXor = countSetBits(xorSum);
let setBitsK = countSetBits(k);
return Math.abs(setBitsXor - setBitsK);
}
const nums = [2, 1, 3, 4];
const k = 1;
console.log(minOperations(nums, k));#include <stdio.h>
int countSetBits(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int minOperations(int* nums, int numsSize, int k) {
int xor_sum = 0;
for (int i = 0; i < numsSize; i++) {
xor_sum ^= nums[i];
}
int set_bits_xor = countSetBits(xor_sum);
int set_bits_k = countSetBits(k);
return abs(set_bits_xor - set_bits_k);
}
int main() {
int nums[] = {2, 1, 3, 4};
int k = 1;
printf("%d\n", minOperations(nums, 4, k));
return 0;
}using System;
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));
}
}Contains a function to count set bits which is used to determine the difference needed in the number of operations.
Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).
Approach 3: Bit Manipulation
We can perform a bitwise XOR operation on all elements in the array nums. The number of bits that differ from the binary representation of k in the result is the minimum number of operations.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function minOperations(nums: number[], k: number): number {
for (const x of nums) {
k ^= x;
}
return bitCount(k);
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func minOperations(nums []int, k int) (ans int) {
for _, x := range nums {
k ^= x
}
return bits.OnesCount(uint(k))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Bit Manipulation | Time Complexity: O(n) |
| Approach 2: Count Set Bits | Time Complexity: O(n + log(max(nums[i]))) |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation with XOR Difference | O(n) | O(1) | General case; fastest way once you recognize XOR properties |
| Count Set Bits (Popcount) | O(n) | O(1) | Useful when built-in bit counting functions are available |
Frequently asked questions
Is Minimum Number of Operations to Make Array XOR Equal to K easy or hard?
The problem is typically classified as Medium difficulty. The implementation is short, but recognizing that the XOR difference directly represents the required bit flips requires familiarity with XOR properties and bit manipulation techniques.
Minimum Number of Operations to Make Array XOR Equal to K Python/Java solution
In Python or Java, compute the XOR of all elements in nums, then calculate diff = xor ^ k. Use built-in functions such as Integer.bitCount(diff) in Java or bin(diff).count('1') in Python to count the number of set bits and return that value.
How to solve Minimum Number of Operations to Make Array XOR Equal to K in O(n)?
First compute the XOR of all numbers in the array. Then compute diff = currentXor ^ k. The minimum number of operations equals the number of set bits in diff, which can be counted using a popcount function or bit tricks like repeatedly applying diff &= diff - 1.
What is the best approach for Minimum Number of Operations to Make Array XOR Equal to K?
The optimal approach computes the XOR of the entire array and compares it with k. Calculate diff = currentXor ^ k and count the number of set bits in diff. Each set bit represents one bit that must be flipped in the array, giving an O(n) time and O(1) space solution.
Is Minimum Number of Operations to Make Array XOR Equal to K asked at Google/Amazon/Meta?
Bit manipulation and XOR-based reasoning problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary in wording, the core concept of using XOR differences and counting set bits is a common interview pattern.
What data structure is used in Minimum Number of Operations to Make Array XOR Equal to K?
The problem primarily uses array traversal and bit manipulation. No additional data structures are required beyond simple variables for computing XOR and counting set bits, keeping the space complexity constant.
What is the time complexity of Minimum Number of Operations to Make Array XOR Equal to K?
The time complexity is O(n) because you must iterate through the array once to compute the total XOR. Counting the set bits of the difference value takes constant time since integers have a fixed bit width (typically 32 bits). Space complexity remains O(1).