Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum XOR for Each Query solution and explanation

MediumArrayBit ManipulationPrefix Sum8 min read84.7% acceptanceUpdated 9 Apr 2026
Asked atUberBloomberg
Practise Maximum XOR for Each Query
27:34
Maximum XOR for Each Query | Simple Explanation | Leetcode 1829 | codestorywithMIKcodestorywithMIK · 27:34 · 9K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum XOR for Each Query | Simple Explanation | Leetcode 1829 | codestorywithMIKcodestorywithMIK · 27:34 · 9K views
  2. Maximum XOR for Each Query - Leetcode 1829 - PythonNeetCodeIO · 11:35 · 7K views
  3. Maximum XOR for Each Query | Leetcode 1829Techdose · 10:25 · 3K views
  4. 1829. Maximum XOR for Each Query (Leetcode Medium)Programming Live with Larry · 10:39 · 2K views
  5. [LEETCODE] 1829. Maximum XOR for Each QueryhalkeyCodie · 22:31 · 778 views
  6. Daily Leetcode #1683: Nov 08, 2024 - 1829. Maximum XOR for Each QueryProgramming Live with Larry · 7:41 · 293 views
  7. XOR prefix sum C++ python解Leetcode 1829 Maximum XOR for Each QueryAn-Wen Deng · 10:21 · 259 views
  8. Maximum XOR for Each Query| LeetCode 1829 | Must do Bit manipulation DSA | Daily Leetcode problemCode Thoughts · 14:27 · 135 views
  9. 1829. Maximum XOR for Each Query | Daily Challenge | 8 Nov 2024 | POTDCTO Bhaiya · 21:10 · 130 views
  10. LeetCode 1829 - Maximum XOR For Each Query - JavaAlpha-Code · 10:51 · 121 views

The 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:

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

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

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

  • nums.length == n
  • 1 <= n <= 105
  • 1 <= maximumBit <= 20
  • 0 <= nums[i] < 2maximumBit
  • nums​​​ is sorted in ascending order.

Approach overview

Problem Overview: You receive an integer array nums and a value maximumBit. For each query, you consider the prefix of the array and choose an integer k (0 ≤ k < 2maximumBit) that maximizes prefixXor ^ k. After each query, the last element of the array is removed. The task is to return the optimal k for every query.

Approach 1: Precompute and Use XOR Properties (Time: O(n), Space: O(n))

This approach relies on a key property of bit manipulation: the value that maximizes x ^ k is the bitwise complement of x within the allowed bit range. First compute the prefix XOR of the entire array using a prefix XOR technique. Let mask = (1 << maximumBit) - 1, which represents the largest number allowed for k. For each query, the best value of k is simply prefixXor ^ mask. After producing the result, remove the last element logically by XOR-ing it out of the running prefix. This avoids recomputing XOR values repeatedly and processes the queries in reverse order.

The strength of this method is its simplicity. You compute the total XOR once, then update it incrementally as the array shrinks. XOR operations are constant time, so the entire algorithm runs in linear time relative to the array size.

Approach 2: Calculate On-The-Fly with Prefix XOR Array (Time: O(n), Space: O(n))

This variation explicitly builds a prefix XOR array where prefix[i] stores the XOR of elements from index 0 to i. Each query corresponds to a prefix length that decreases over time. Instead of modifying a running XOR variable, you directly reference the appropriate prefix value. For the current prefix XOR value x, compute the optimal answer using the same mask trick: k = x ^ mask. Because XOR with the mask flips all bits within the allowed range, the result produces the maximum possible XOR value.

The main difference is clarity versus memory usage. Using a prefix array can make debugging easier because every prefix XOR is stored explicitly. However, it requires extra memory compared with maintaining a single running XOR.

Recommended for interviews: The expected solution uses XOR properties with a running prefix value and a bitmask. Interviewers want to see recognition that maximizing x ^ k means flipping every bit within the allowed range. Starting with the straightforward prefix XOR idea demonstrates understanding, while deriving the mask trick shows strong comfort with bitwise operations. The optimal implementation runs in O(n) time with O(1) auxiliary space.

Approach 1: Approach 1: Precompute and Use XOR Properties

In this approach, we compute the total XOR of the array and then, for each query, determine the best integer k to maximize the XOR. We leverage the fact that XOR of a number with itself is 0, and XOR with 0 is the number itself. The trick is to use the maximum number in the range [0, 2^maximumBit) as an XOR mask to get the maximum number at each step.

We'll precompute the total XOR of the given array. For each step, find k by XORing the current XOR value with the maximum possible number, which is `(2^maximumBit - 1)`. After each query, remove the last element and update the XOR till it becomes empty.

def maxXorQueries(nums, maximumBit):
    max_num = (1 << maximumBit) - 1
    total_xor = 0
    result = []
    for num in nums:
        total_xor ^= num
    for num in reversed(nums):
        result.append(total_xor ^ max_num)
        total_xor ^= num
    return result

nums = [0, 1, 1, 3]
maximumBit = 2
print(maxXorQueries(nums, maximumBit))
import java.util.*;

public class MaxXorQueries {
    public static int[] maxXorQueries(int[] nums, int maximumBit) {
        int maxNum = (1 << maximumBit) - 1;
        int totalXor = 0;
        int[] result = new int[nums.length];
        for (int num : nums) {
            totalXor ^= num;
        }
        for (int i = 0; i < nums.length; ++i) {
            result[i] = totalXor ^ maxNum;
            totalXor ^= nums[nums.length - 1 - i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 1, 3};
        int maximumBit = 2;
        int[] result = maxXorQueries(nums, maximumBit);
        for (int ans : result) {
            System.out.print(ans + " ");
        }
    }
}
#include <iostream>
#include <vector>
using namespace std;

vector<int> maxXorQueries(vector<int>& nums, int maximumBit) {
    int maxNum = (1 << maximumBit) - 1;
    int totalXor = 0;
    vector<int> result(nums.size());
    for (int num : nums) {
        totalXor ^= num;
    }
    for (int i = 0; i < nums.size(); ++i) {
        result[i] = totalXor ^ maxNum;
        totalXor ^= nums[nums.size() - 1 - i];
    }
    return result;
}

int main() {
    vector<int> nums = {0, 1, 1, 3};
    int maximumBit = 2;
    vector<int> result = maxXorQueries(nums, maximumBit);
    for (int ans : result) {
        cout << ans << " ";
    }
    return 0;
}
function maxXorQueries(nums, maximumBit) {
    const maxNum = (1 << maximumBit) - 1;
    let totalXor = 0;
    const result = new Array(nums.length);
    for (const num of nums) {
        totalXor ^= num;
    }
    for (let i = 0; i < nums.length; ++i) {
        result[i] = totalXor ^ maxNum;
        totalXor ^= nums[nums.length - 1 - i];
    }
    return result;
}

const nums = [0, 1, 1, 3];
const maximumBit = 2;
console.log(maxXorQueries(nums, maximumBit));
#include <stdio.h>

void maxXorQueries(int *nums, int n, int maximumBit, int *result) {
    int maxNum = (1 << maximumBit) - 1;
    int totalXor = 0;
    for (int i = 0; i < n; ++i) {
        totalXor ^= nums[i];
    }
    for (int i = 0; i < n; ++i) {
        result[i] = totalXor ^ maxNum;
        totalXor ^= nums[n - 1 - i];
    }
}

int main() {
    int nums[] = {0, 1, 1, 3};
    int maximumBit = 2;
    int n = sizeof(nums) / sizeof(nums[0]);
    int result[n];
    maxXorQueries(nums, n, maximumBit, result);
    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}
using System;

class MaxXorQueries {
    public static int[] MaxXorQueries(int[] nums, int maximumBit) {
        int maxNum = (1 << maximumBit) - 1;
        int totalXor = 0;
        int[] result = new int[nums.Length];
        foreach (int num in nums) {
            totalXor ^= num;
        }
        for (int i = 0; i < nums.Length; ++i) {
            result[i] = totalXor ^ maxNum;
            totalXor ^= nums[nums.Length - 1 - i];
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] nums = {0, 1, 1, 3};
        int maximumBit = 2;
        int[] result = MaxXorQueries(nums, maximumBit);
        Console.WriteLine(string.Join(" ", result));
    }
}

The function maxXorQueries generates the results by first computing the XOR for the complete array and then using this with the XOR mask within a reverse pass, erasing the effect of each considered number iteratively.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) for the result.

Try this approach in the editor

Approach 2: Approach 2: Calculate On-The-Fly with Prefix XOR Array

This approach calculates the XOR using prefix sums for XOR which allows direct computation of the desired XOR values for any subset by removing the influence of past elements efficiently. We combine this with the known max number XOR mask strategy to derive each query's answer.

First, we compute the prefix XOR array which gives cumulative XOR up to any index. By doing so, calculating new ranges becomes direct through array subtraction for the prefix array indices, because of the property (A XOR A = 0) property that cancels out all elements between boundaries.

def maxXorQueriesPrefix(nums, maximumBit):
    max_num = (1 << maximumBit) - 1
    prefix_xor = [0] * len(nums)
    result = []
    prefix_xor[0] = nums[0]
    for i in range(1, len(nums)):
        prefix_xor[i] = prefix_xor[i - 1] ^ nums[i]
    for i in range(len(nums)):
        current_xor = prefix_xor[-1] if i == 0 else prefix_xor[-1] ^ prefix_xor[i - 1]
        result.append(current_xor ^ max_num)
    return result

nums = [0, 1, 1, 3]
maximumBit = 2
print(maxXorQueriesPrefix(nums, maximumBit))
import java.util.*;

public class MaxXorQueriesPrefix {
    public static int[] maxXorQueriesPrefix(int[] nums, int maximumBit) {
        int maxNum = (1 << maximumBit) - 1;
        int[] prefixXor = new int[nums.length];
        int[] result = new int[nums.length];
        prefixXor[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            prefixXor[i] = prefixXor[i - 1] ^ nums[i];
        }
        for (int i = 0; i < nums.length; ++i) {
            int currentXor = (i == 0) ? prefixXor[nums.length - 1] : prefixXor[nums.length - 1] ^ prefixXor[i - 1];
            result[i] = currentXor ^ maxNum;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 1, 3};
        int maximumBit = 2;
        int[] result = maxXorQueriesPrefix(nums, maximumBit);
        for (int ans : result) {
            System.out.print(ans + " ");
        }
    }
}
#include <iostream>
#include <vector>
using namespace std;

vector<int> maxXorQueriesPrefix(const vector<int>& nums, int maximumBit) {
    int maxNum = (1 << maximumBit) - 1;
    vector<int> prefixXor(nums.size());
    vector<int> result(nums.size());
    prefixXor[0] = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        prefixXor[i] = prefixXor[i - 1] ^ nums[i];
    }
    for (size_t i = 0; i < nums.size(); ++i) {
        int currentXor = ((i == 0) ? prefixXor[nums.size() - 1] : prefixXor[nums.size() - 1] ^ prefixXor[i - 1]);
        result[i] = currentXor ^ maxNum;
    }
    return result;
}

int main() {
    vector<int> nums = {0, 1, 1, 3};
    int maximumBit = 2;
    vector<int> result = maxXorQueriesPrefix(nums, maximumBit);
    for (int ans : result) {
        cout << ans << " ";
    }
    return 0;
}
function maxXorQueriesPrefix(nums, maximumBit) {
    const maxNum = (1 << maximumBit) - 1;
    const prefixXor = new Array(nums.length);
    const result = new Array(nums.length);
    prefixXor[0] = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        prefixXor[i] = prefixXor[i - 1] ^ nums[i];
    }
    for (let i = 0; i < nums.length; ++i) {
        const currentXor = (i === 0) ? prefixXor[nums.length - 1] : prefixXor[nums.length - 1] ^ prefixXor[i - 1];
        result[i] = currentXor ^ maxNum;
    }
    return result;
}

const nums = [0, 1, 1, 3];
const maximumBit = 2;
console.log(maxXorQueriesPrefix(nums, maximumBit));
#include <stdio.h>

void maxXorQueriesPrefix(int *nums, int n, int maximumBit, int *result) {
    int maxNum = (1 << maximumBit) - 1;
    int prefixXor[n];
    prefixXor[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefixXor[i] = prefixXor[i - 1] ^ nums[i];
    }
    for (int i = 0; i < n; ++i) {
        int currentXor = (i == 0) ? prefixXor[n - 1] : prefixXor[n - 1] ^ prefixXor[i - 1];
        result[i] = currentXor ^ maxNum;
    }
}

int main() {
    int nums[] = {0, 1, 1, 3};
    int maximumBit = 2;
    int n = sizeof(nums) / sizeof(nums[0]);
    int result[n];
    maxXorQueriesPrefix(nums, n, maximumBit, result);
    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}
using System;

class MaxXorQueriesPrefix {
    public static int[] MaxXorQueriesPrefix(int[] nums, int maximumBit) {
        int maxNum = (1 << maximumBit) - 1;
        int[] prefixXor = new int[nums.Length];
        int[] result = new int[nums.Length];
        prefixXor[0] = nums[0];
        for (int i = 1; i < nums.Length; ++i) {
            prefixXor[i] = prefixXor[i - 1] ^ nums[i];
        }
        for (int i = 0; i < nums.Length; ++i) {
            int currentXor = (i == 0) ? prefixXor[nums.Length - 1] : prefixXor[nums.Length - 1] ^ prefixXor[i - 1];
            result[i] = currentXor ^ maxNum;
        }
        return result;
    }

    public static void Main(string[] args) {
        int[] nums = {0, 1, 1, 3};
        int maximumBit = 2;
        int[] result = MaxXorQueriesPrefix(nums, maximumBit);
        Console.WriteLine(string.Join(" ", result));
    }
}

Here, maxXorQueriesPrefix precomputes a prefix XOR list. The computation and determination of maximum XOR value is done efficiently due to cumulative XOR properties enabled by using prefix XOR.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) for the prefix XOR array.

Try this approach in the editor

Approach 3: Bitwise Operation + Enumeration

First, we preprocess the XOR sum xs of the array nums, i.e., xs=nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1].

Next, we enumerate each element x in the array nums from back to front. The current XOR sum is xs. We need to find a number k such that the value of xs \oplus k is as large as possible, and k \lt 2^{maximumBit}.

That is to say, we start from the maximumBit - 1 bit of xs and enumerate to the lower bit. If a bit of xs is 0, then we set the corresponding bit of k to 1. Otherwise, we set the corresponding bit of k to 0. In this way, the final k is the answer to each query. Then, we update xs to xs \oplus x and continue to enumerate the next element.

The time complexity is O(n times m), where n and m are the values of the array nums and maximumBit respectively. Ignoring the space consumption of the answer, the space complexity is O(1).

function getMaximumXor(nums: number[], maximumBit: number): number[] {
    let xs = 0;
    for (const x of nums) {
        xs ^= x;
    }
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
        const x = nums[n - i - 1];
        let k = 0;
        for (let j = maximumBit - 1; j >= 0; --j) {
            if (((xs >> j) & 1) == 0) {
                k |= 1 << j;
            }
        }
        ans[i] = k;
        xs ^= x;
    }
    return ans;
}
func getMaximumXor(nums []int, maximumBit int) (ans []int) {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	for i := range nums {
		x := nums[len(nums)-i-1]
		k := 0
		for j := maximumBit - 1; j >= 0; j-- {
			if xs>>j&1 == 0 {
				k |= 1 << j
			}
		}
		ans = append(ans, k)
		xs ^= x
	}
	return
}
Try this approach in the editor

Approach 4: Enumeration Optimization

Similar to Solution 1, we first preprocess the XOR sum xs of the array nums, i.e., xs=nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1].

Next, we calculate 2^{maximumBit} - 1, which is 2^{maximumBit} minus 1, denoted as mask. Then, we enumerate each element x in the array nums from back to front. The current XOR sum is xs, then k=xs \oplus mask is the answer to each query. Then, we update xs to xs \oplus x and continue to enumerate the next element.

The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer, the space complexity is O(1).

function getMaximumXor(nums: number[], maximumBit: number): number[] {
    let xs = 0;
    for (const x of nums) {
        xs ^= x;
    }
    const mask = (1 << maximumBit) - 1;
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
        const x = nums[n - i - 1];
        let k = xs ^ mask;
        ans[i] = k;
        xs ^= x;
    }
    return ans;
}
func getMaximumXor(nums []int, maximumBit int) (ans []int) {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	mask := (1 << maximumBit) - 1
	for i := range nums {
		x := nums[len(nums)-i-1]
		k := xs ^ mask
		ans = append(ans, k)
		xs ^= x
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Precompute and Use XOR Properties

Time Complexity: O(n)
Space Complexity: O(n) for the result.

Approach 2: Calculate On-The-Fly with Prefix XOR Array

Time Complexity: O(n)
Space Complexity: O(n) for the prefix XOR array.

Bitwise Operation + Enumeration–
Enumeration Optimization–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force XOR for Each QueryO(n^2)O(1)Useful only for understanding the problem constraints or validating small test cases
Precompute and Use XOR PropertiesO(n)O(1)Best general solution; uses XOR mask trick and updates prefix XOR as elements are removed
Prefix XOR ArrayO(n)O(n)When you want explicit prefix values for clarity or debugging

Frequently asked questions

Is Maximum XOR for Each Query easy or hard?

Maximum XOR for Each Query is classified as a Medium problem. The implementation is straightforward once you recognize the XOR mask trick, but identifying that the maximum XOR comes from flipping all bits within the allowed range requires familiarity with bit manipulation patterns.

Maximum XOR for Each Query Python/Java solution

Python and Java implementations both follow the same logic: compute the total XOR, create the mask (1 << maximumBit) - 1, and iterate from the end of the array while updating the XOR. Each iteration calculates the best k using XOR with the mask and appends it to the result list.

How to solve Maximum XOR for Each Query in O(n)?

First compute the XOR of all numbers in the array. Build a mask using (1 << maximumBit) - 1, which represents the largest allowed value for k. For each query, compute k = currentXor ^ mask to maximize the XOR result, append it to the answer, and then remove the last element from the running XOR. Each step is constant time, producing an O(n) algorithm.

What is the best approach for Maximum XOR for Each Query?

The optimal approach uses XOR properties with a bitmask. Compute the XOR of the entire array, create a mask equal to (1 << maximumBit) - 1, and for each query return prefixXor ^ mask. After producing an answer, remove the last element from the prefix using XOR. This solution runs in O(n) time with O(1) extra space.

Is Maximum XOR for Each Query asked at Google/Amazon/Meta?

This problem represents a common interview pattern around bit manipulation and prefix XOR. Variations of XOR maximization and prefix XOR queries appear in interviews at companies like Amazon, Google, and Meta, especially for roles that test low-level algorithmic thinking.

What data structure is used in Maximum XOR for Each Query?

The solution mainly relies on bit manipulation and prefix XOR computation rather than complex data structures. Some implementations use a prefix XOR array to store cumulative XOR values, while the optimal version keeps a single running XOR variable and updates it as elements are removed.

What is the time complexity of Maximum XOR for Each Query?

The optimal solution runs in O(n) time where n is the length of the array. You compute the initial prefix XOR once and then update it in constant time for each query. Space complexity can be O(1) if you keep a running XOR variable, or O(n) if you store a prefix XOR array.

Comments

Next problem · similarCount the Number of Beautiful SubarraysMedium
Now write it yourselfClose this page and solve Maximum XOR for Each Query in the editor, without looking.
Practise Maximum XOR for Each Query