Minimum Number of Operations to Make Array XOR Equal to K

Minimum Number of Operations to Make Array XOR Equal to K - 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 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: You can flip leading zero bits in the binary representation of elements. For example, for the number (101)₂ you can flip the fourth bit and obtain (1101)₂.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,4], k = 1

› Output: 2

💡 Note: Current XOR = 2⊕1⊕3⊕4 = 4. To get k=1, we need 4⊕1=5. Binary 5 = 101 has 2 bits set, so 2 operations needed.

Example 2 — Already Equal

$ Input: nums = [2,0,2,0], k = 0

› Output: 0

💡 Note: Current XOR = 2⊕0⊕2⊕0 = 0, which equals k=0. No operations needed.

Example 3 — Single Element

$ Input: nums = [5], k = 3

› Output: 2

💡 Note: Current XOR = 5. To get k=3, we need 5⊕3=6. Binary 6 = 110 has 2 bits set, so 2 operations needed.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁶
0 ≤ k ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,3,4] with target k=1

Calculate XOR

Find XOR of all elements = 4

Compare & Count

4⊕1=5, count bits in 5 = 2 operations

Key Takeaway

🎯 Key Insight: Only the bit positions where current XOR differs from target K need to be flipped

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is that we only need to count differing bits between the current XOR and target K. Best approach is bit manipulation - calculate array XOR, compare with K, and count different bits. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimal Bit Manipulation	O(n)	O(1)	Compare current XOR with target K bit by bit
Brute Force	O(2^(n×32))	O(1)	Try all possible bit flip combinations to reach target XOR

Optimal Bit Manipulation — Algorithm Steps

Step 1: Calculate XOR of all array elements
Step 2: XOR the result with target K to find differing bits
Step 3: Count number of 1-bits in the difference (each represents one required flip)

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate XOR

XOR all array elements together

Compare with K

XOR result with target to find differences

Count Bits

Count 1-bits in difference

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n, int k) {
    // Calculate XOR of all elements
    int currentXor = 0;
    for (int i = 0; i < n; i++) {
        currentXor ^= nums[i];
    }
    
    // Find difference between current XOR and target
    int diff = currentXor ^ k;
    
    // Count number of 1-bits in difference
    int operations = 0;
    while (diff) {
        operations += diff & 1;
        diff >>= 1;
    }
    
    return operations;
}

int main() {
    int nums[1000];
    int n = 0, k;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    char* ptr = line + 1; // Skip [
    char* token = strtok(ptr, ",]\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]\n");
    }
    
    scanf("%d", &k);
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to calculate XOR, plus constant time bit counting

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for XOR calculation and bit counting

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler