XOR Queries of a Subarray
A medium Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 1
- Core for
- 9 roles
The problem
Given an integer array and a list of queries where each query specifies a range [left, right], return an array where each element is the XOR of all elements from index left to index right (inclusive).
Example 1
- Input
- arr = [5,2,9,3], queries = [[0,1], [1,2], [0,3], [2,2]]
- Output
- [7, 11, 13, 9]
- Why
- 5^2=7, 2^9=11, 5^2^9^3=13 and the single element 9.
Example 2
- Input
- arr = [6,1,7,2], queries = [[1,3], [0,2], [3,3], [0,0]]
- Output
- [4, 0, 2, 6]
- Why
- 1^7^2=4, 6^1^7=0, then the single elements 2 and 6.
Constraints
- 1 <= arr.length <= 3 * 10^4
- 1 <= queries.length <= 3 * 10^4
- 0 <= arr[i] <= 10^9
- 0 <= left <= right < arr.length
How to think about it
Updated 2026-09-29XOR is its own inverse operation: x ^ x = 0. Just as prefix sums allow range sums through subtraction, prefix XORs allow range queries because XORing out the prefix before the range cancels all elements preceding the query start. A range query reduces to combining two prefix checkpoints.
Approaches, worst first
Brute force range iteration
time O(q * n) · space O(1)
For each query [left, right], loop from left to right XORing values together. Straightforward, but repeats identical subarray traversals across queries and degrades to quadratic time.
Prefix XOR prefix arrayWrite this one
time O(n + q) · space O(n)
Precompute a prefix XOR array where pref[k] stores the cumulative XOR up to index k. Any query [left, right] is answered in constant time via pref[right] ^ pref[left - 1], or by overwriting the original array in place.
Where people lose marks · 2
- Failing to handle queries starting at `left = 0` causes index out-of-bounds when evaluating `pref[left - 1]`; either use a 1-indexed prefix table of size n + 1 or branch when left is zero.
- Modifying the input array in place when reusing it as the prefix array might violate caller expectations if immutability is required.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
More Bit Manipulation problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .