Skip to main content
Talentd

Minimum Number of Operations to Make Array XOR Equal to K - Solution & Explanation

MediumArrayBit Manipulation14 min readAsked at: Amazon, American Express, Auriga
Practice this problem

Problem Statement

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

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.

We 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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

We 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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Bit Manipulation

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.

Approach 2: Count Set Bits

Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Manipulation with XOR DifferenceO(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

Video Solution

Minimum Number of Operations to Make Array XOR Equal to K | Easy | Leetcode 2997 | codestorywithMIK • codestorywithMIK • 7,778 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Minimum Number of Operations to Make Array XOR Equal to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Bit Flips to Convert Number