Vultr DocsLatest Content

Minimum Number of Operations to Make Array XOR Equal to K

Updated on 15 July, 2025
Minimum Number of Operations to Make Array XOR Equal to K header image

Problem Statement

The objective of this problem is to determine the minimum number of bit flips required to modify elements in a given array nums such that the cumulative bitwise XOR of all elements in the array equals a given integer k. The operation allowed involves choosing any element from the array and flipping a bit in its binary representation. A bit flip means altering a bit from 0 to 1 or vice versa. This could also include flipping any leading zeros in the binary representation of a number.

Examples

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 <= 105
  • 0 <= nums[i] <= 106
  • 0 <= k <= 106

Approach and Intuition

  1. Begin by calculating the XOR of all items in the initial array, referred to as xor_all. This will be the cumulative result of XOR-ing every element together.
  2. Evaluate the difference between xor_all and the desired XOR result k using another XOR operation: xor_needed = xor_all XOR k. This operation essentially identifies which bits are different between xor_all and k.
  3. The goal now is to flip the necessary bits in the array to turn xor_all into k. xor_needed tells us which bits we need to change.
  4. For each bit that is set (i.e., is 1) in xor_needed, determine how many bits in the corresponding positions in numbers from nums need flipping. This is because each bit in xor_needed that is set represents a disparity between the current xor_all and k.
  5. For each set bit in xor_needed, perform the following sub-steps:
    • Count the zeros at that bit position across all numbers in nums. This count is essential because it informs us how many 0-to-1 flips are needed.
    • Alternatively, count the ones at that bit position for potential 1-to-0 flips.
    • Choose the lesser count between zeros and ones because that will require fewer flips to achieve the desired bit state across all numbers.
  6. Sum all the minimum counts of required flips from the above step; this sum will be the minimum number of operations needed to make the cumulative XOR of the array equal to k.

The approach utilizes properties of XOR operations effectively to isolate the differences needed and strategically count bit flips, minimizing the total operations.

Solutions

  • C++
cpp 
class Solution {
public:
    int minimumOperations(vector<int>& numbers, int target) {
        int xorSum = 0;
        for (int value : numbers) {
            xorSum ^= value;
        }
            
        return __builtin_popcount(xorSum ^ target);
    }
};

The provided C++ code defines a function, minimumOperations, intended to determine the minimum number of operations required to make the XOR of an array equal to a specified target value (denoted as target in the code). The function accomplishes this by executing the following steps:

  1. Initialize xorSum to zero. This variable will store the cumulative XOR of all elements in the input array numbers.
  2. Iterate over each element in the array numbers and perform a XOR operation with xorSum.
  3. Compute the XOR of xorSum and target to find the difference that needs to be corrected.
  4. Use the __builtin_popcount function to count the number of 1's in the binary representation of the result from the previous step. This count represents the minimum number of operations needed, where each operation involves flipping a bit.

This function effectively uses bitwise operations to analyze the discrepancy between the current XOR of the array and the desired XOR (target). The use of __builtin_popcount serves as a direct method to quantify the minimum changes required by counting the differing bits.

  • Java
java 
class Solution {
    public int minimumSteps(int[] array, int target) {
        int resultXor = 0;
        for (int num : array) {
            resultXor ^= num;
        }
            
        return Integer.bitCount(resultXor ^ target);
    }
}

To solve the problem of determining the minimum number of operations required to make the XOR of an array equal to a given target value, consider the following breakdown using Java:

  • Initialize a variable resultXor to zero to hold the cumulative XOR of all elements in the array.
  • Iterate through each element in the array, updating resultXor by XORing it with the current element. This computes the XOR for the entire array.
  • Determine the number of differing bits between resultXor and the target integer. This is achieved by XORing resultXor with the target to highlight bits that differ between the two values and then counting these bits using Integer.bitCount.
  • The count from the previous step directly indicates the minimum number of operations required. Each differing bit represents a required operation to flip that particular bit to match the target.

This method provides a straightforward and efficient way to compute the necessary transformations, leveraging the properties of the XOR operation and bit manipulation functions available in Java.

  • Python
python 
class Solution:
    def minimumOperations(self, numbers: List[int], target: int) -> int:
        result_xor = 0
        for number in numbers:
            result_xor ^= number
            
        return bin(result_xor ^ target).count('1')

The function minimumOperations accepts two parameters: a list of integers called numbers and a single integer named target. The goal is to determine the minimum number of operations required to make the XOR of all elements in the numbers list equal to target.

  • Initialize result_xor to zero.
  • XOR all elements in numbers using a loop, updating result_xor.
  • XOR the result of the aggregation (result_xor) with target.
  • Convert the final XOR result to its binary form and count the number of '1's, which represent the necessary operations to transform the combined XOR of the list to the target value.

The number of '1's counted in the binary form of the final XOR result is returned, indicating the minimum number of operations needed. This solution effectively uses bitwise operations to achieve the desired outcome.

Comments