Scale Engineer

Minimum Number of Operations to Make Array XOR Equal to K

Med
#2665Time: O(N * M), where N is the number of elements in `nums` and M is the number of bits considered (e.g., 31). The nested loops (iterating through bits and then through the array) result in this complexity.Space: O(1), as we only use a few variables to store intermediate results like the current bit and the total operation count.1 company
Patterns
Bit Manipulation
Data structures
Array
Companies
American Express

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach analyzes the problem one bit at a time. For each bit position, it determines if a flip is necessary to match the target k's corresponding bit. The total number of required flips across all bit positions gives the minimum number of operations.

Algorithm

  • Initialize an operations counter to 0.
  • Iterate through each bit position i from 0 up to a safe limit (e.g., 30).
  • For each bit i, calculate the i-th bit of the current XOR sum of nums by checking the parity of the count of numbers with the i-th bit set.
  • Get the i-th bit of the target k.
  • If the two bits differ, increment the operations counter.
  • Return the total operations.

Walkthrough

The core idea is that a flip at the i-th bit of any number in the array will flip the i-th bit of the total XOR sum of the array. We can iterate through each bit position and check if the bit of the current XOR sum matches the corresponding bit of k. If they don't match, one operation (a bit flip at that position) is required.

  • Algorithm:
    1. Initialize an operations counter to 0.
    2. Iterate through each bit position i from 0 up to a safe limit (e.g., 30, since the maximum value of nums[i] and k is 10^6, which is less than 2^20).
    3. For each bit position i, calculate the i-th bit of the current XOR sum of nums. This can be done by iterating through all numbers in nums and counting how many have the i-th bit set. If the count is odd, the XOR sum's i-th bit is 1; otherwise, it's 0.
    4. Get the i-th bit of the target value k.
    5. If the calculated i-th bit of the XOR sum differs from the i-th bit of k, it means we need to perform one flip at this bit position. Increment the operations counter.
    6. After checking all relevant bit positions, the operations counter will hold the minimum number of operations.
class Solution {    public int minOperations(int[] nums, int k) {        int operations = 0;        // Max value is 10^6, which is < 2^20. Checking up to 30 bits is safe.        for (int i = 0; i < 31; i++) {            int currentXorBit = 0;            for (int num : nums) {                // Check if the i-th bit is set in num                if (((num >> i) & 1) == 1) {                    currentXorBit ^= 1;                }            }                        // Get the i-th bit of k            int kBit = (k >> i) & 1;                        // If the bits don't match, one operation is needed for this bit position            if (currentXorBit != kBit) {                operations++;            }        }        return operations;    }}

Complexity

Time

O(N * M), where N is the number of elements in `nums` and M is the number of bits considered (e.g., 31). The nested loops (iterating through bits and then through the array) result in this complexity.

Space

O(1), as we only use a few variables to store intermediate results like the current bit and the total operation count.

Trade-offs

Pros

  • Conceptually straightforward, breaking the problem down by individual bits.

  • Does not require deep insights into the aggregate properties of XOR.

Cons

  • Inefficient due to the nested loop structure, leading to a higher time complexity.

  • It re-scans the entire array for each bit position, which is redundant.

Solutions

class Solution {public  int minOperations(int[] nums, int k) {    for (int x : nums) {      k ^= x;    }    return Integer.bitCount(k);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem