Maximum XOR for Each Query - Practice Coding Problems

Maximum XOR for Each Query - Problem

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,1,3], maximumBit = 2

› Output: [0,3,2,3]

💡 Note: Query 1: XOR of [0,1,1,3] = 3, optimal k = 0 (3⊕0 = 3, maximum for 2 bits). Query 2: XOR of [0,1,1] = 0, optimal k = 3 (0⊕3 = 3). Query 3: XOR of [0,1] = 1, optimal k = 2 (1⊕2 = 3). Query 4: XOR of [0] = 0, optimal k = 3 (0⊕3 = 3).

Example 2 — Single Element

$ Input: nums = [2], maximumBit = 3

› Output: [5]

💡 Note: XOR of [2] = 2 (binary: 010). Maximum value with 3 bits is 7 (binary: 111). Optimal k = 2⊕7 = 5 (binary: 101), giving result 2⊕5 = 7.

Example 3 — Larger maximumBit

$ Input: nums = [0,1,2,2,5,7], maximumBit = 3

› Output: [4,3,6,4,6,7]

💡 Note: Each query finds k that maximizes XOR with current subarray. The maximum possible result is always 2^maximumBit - 1 = 7.

Constraints

nums.length == n
1 ≤ n ≤ 10⁵
1 ≤ maximumBit ≤ 20
0 ≤ nums[i] < 2^maximumBit
nums is sorted in ascending order

Visualization

Tap to expand

Understanding the Visualization

Input

Array [0,1,1,3] with maximumBit=2

Process

Find k that maximizes XOR, then remove last element

Output

Array [0,3,2,3] of optimal k values

Key Takeaway

🎯 Key Insight: To maximize A⊕k, set k = A⊕(all 1s within maximumBit range)

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is that to maximize A XOR k, we need k to be the bitwise complement of A within the maximumBit range. The optimal approach maintains a running XOR and calculates k = totalXOR ^ ((1 << maximumBit) - 1) for each query. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimal Solution	O(n)	O(1)	Calculate XOR incrementally and use bit complement for instant optimal k
Brute Force	O(n² × 2^maximumBit)	O(1)	Try all possible k values for each query to find maximum XOR
Prefix XOR with Bit Manipulation	O(n²)	O(n)	Use prefix XOR and bit flipping to find optimal k instantly

Single Pass Optimal Solution — Algorithm Steps

Start from the end of array
Maintain running XOR as we process elements
For each query, k = currentXOR ^ ((1 << maximumBit) - 1)
Add current element to XOR for next iteration

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total XOR

XOR all elements: 0⊕1⊕1⊕3 = 3

Find Optimal K

k = totalXOR ^ maxVal = 3 ^ 3 = 0

Update for Next Query

Remove last element from XOR

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int maximumBit, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    // Calculate total XOR of all elements
    int totalXor = 0;
    for (int i = 0; i < numsSize; i++) {
        totalXor ^= nums[i];
    }
    
    // Maximum possible value with maximumBit bits
    int maxVal = (1 << maximumBit) - 1;
    
    // Process queries from right to left
    for (int i = 0; i < numsSize; i++) {
        // To maximize totalXor ^ k, we need k = totalXor ^ maxVal
        result[i] = totalXor ^ maxVal;
        
        // Remove the last element for next query
        totalXor ^= nums[numsSize - 1 - i];
    }
    
    *returnSize = numsSize;
    return result;
}

int main() {
    // Parse input array
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int maximumBit;
    scanf("%d", &maximumBit);
    
    int returnSize;
    int* result = solution(nums, numsSize, maximumBit, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for XOR and result array

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Single Pass Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler