Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
XOR together the XORs of every contiguous subarray. Brute force enumerates all subarrays: O(n²). The combinatorial insight: element arr[i] appears in exactly (i+1)·(n−i) subarrays, and XOR only keeps elements that appear an ODD number of times. (i+1)·(n−i) is odd only when both factors are odd, which needs i even AND n odd. So if n is even the answer is 0; if n is odd the answer is the XOR of the elements at even indices (0-based). That's O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can replace enumerating all O(n²) subarrays with a counting argument: how many subarrays include index i, and which counts are odd under XOR cancellation.
Where candidates slip
Brute-forcing all subarrays and timing out, or getting the index parity wrong (odd vs even indices), or forgetting that an even-length array always yields 0.
How to stand out
Derive (i+1)(n−i), note XOR keeps only odd counts, conclude n even → 0 and n odd → XOR of even indices, and deliver it in one O(n) pass.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewXOR over all subarray XORsEnumerate subarrays?YesCount insteadExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Enumerate Every Subarray
1Hint 1Explore hintHide hint
The answer is the XOR of every contiguous subarray's XOR. Generate them all.
2Hint 2Explore hintHide hint
Outer loop fixes the left end i; inner loop extends the right end j, maintaining a running XOR of arr[i..j].
3Hint 3Explore hintHide hint
XOR each running value into a global accumulator. Two nested loops → O(n²).
A · Core idea
Compute the definition directly.
The construction. Fix a left endpoint i. Walk a right endpoint j from i to n−1, keeping a running XOR x = arr[i] ^ arr[i+1] ^ … ^ arr[j]. Each value of x is one subarray's XOR; fold it into a global accumulator result.
Why the running XOR. Recomputing each subarray's XOR from scratch would be O(n³). Extending the previous subarray by one element is a single XOR, dropping the per-subarray cost to O(1) and the total to O(n²).
Why it doesn't scale. With n = 10⁵, n²/2 ≈ 5×10⁹ operations exceed the time budget. The fix is to stop enumerating and instead count how many subarrays each element lands in — then only odd counts matter.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [1, 2, 3]Interactive diagram
Running XOR per left endpoint
i=0Each left endpoint sweeps right, folding running XORs.
2C · Code with teaching comments
Reference implementation previewpublic int sansaXor(int[] arr) { int result = 0; int n = arr.length; for (int i = 0; i < n; i++) { int running = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Each element is XORed in once per subarray that contains it. Brute force discovers that implicitly; the optimal approach counts it directly with (i+1)(n−i) and keeps only odd parity.
ComplexityO(n²) time, O(1) space — There are n(n+1)/2 subarrays; maintaining a running XOR makes each O(1), so total work is O(n²) — fine for small n, too slow at 10⁵.
E · Edge cases and pitfalls3Recomputing each subarray's XOR from scratch — turns O(n²) into O(n³).Explore edge casesHide edge cases
Pitfalls
- Recomputing each subarray's XOR from scratch — turns O(n²) into O(n³).
- Resetting running outside the i-loop so subarrays bleed across left endpoints.
- Relying on this for n up to 10⁵ — it times out.
Approach 2 of 2 · Optimal
Parity Count — XOR Even Indices When n Is Odd (Optimal)
1Hint 1Explore hintHide hint
How many subarrays contain index i? Pick any left end in 0..i and any right end in i..n−1: (i+1)·(n−i).
2Hint 2Explore hintHide hint
XOR keeps an element only if it appears an odd number of times. When is (i+1)(n−i) odd?
3Hint 3Explore hintHide hint
A product is odd only when both factors are odd: i+1 odd (i even) AND n−i odd. If n is even that's impossible → 0; if n is odd it forces i even.
A · Core idea
Replace enumeration with a parity argument.
Count the occurrences. Index i appears in subarray arr[l..r] whenever l ≤ i ≤ r. There are i + 1 valid left ends (0..i) and n − i valid right ends (i..n−1), so index i appears in exactly (i + 1)·(n − i) subarrays — and is XORed in that many times across all subarray XORs.
Only odd counts survive. Since x ^ x = 0, an element folded in an even number of times cancels to 0. So arr[i] contributes iff (i + 1)·(n − i) is odd.
When is the product odd? A product of integers is odd only if every factor is odd. So we need i + 1 odd (i.e. i even) AND n − i odd. Given i even, n − i is odd exactly when n is odd. Two consequences:
- If
nis even,n − iandi + 1can't both be odd for anyi→ no element survives → the answer is 0. - If
nis odd, the survivors are precisely the even indices0, 2, 4, …→ the answer is the XOR of the even-indexed elements.
Why it's correct and fast. This is exactly the brute-force fold, regrouped by element and reduced by parity — same value, computed in one linear scan (or a constant-time return when n is even).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [1, 2, 3] (n = 3, odd)Interactive diagram
Occurrence parity decides survival
n parity(i+1)(n−i) odd only at even i when n is odd.
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The whole double loop collapses to one question per element: is the number of subarrays containing it odd? That count is (i+1)(n−i), odd only at even indices of an odd-length array. Cancellation does all the work.
ComplexityO(n) time, O(1) space — Either return 0 immediately (n even) or one pass over the even indices (n odd) — O(n) time, O(1) space.
E · Edge cases and pitfalls6arr = [9] (n = 1) — n odd; only even index 0 → result = arr[0] = 9.Explore edge casesHide edge cases
Edge cases handled
arr = [9] (n = 1)n odd; only even index 0 → result = arr[0] = 9.arr = [4, 5, 7, 5] (n = 4)n even → return 0 immediately; all contributions cancel.arr = [2, 3] (n = 2)n even → 0. Check: [2]^[3]^[2,3] = 2^3^1 = 0.
Pitfalls
- Using 1-based indexing and XORing the wrong parity of positions.
- Forgetting the n-even shortcut and still scanning (works but misses the clean reasoning).
- Stepping i by 1 and conditionally checking parity inside — correct but step-by-2 is cleaner and faster.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int sansaXor(int[] arr) { int n = arr.length; if (n % 2 == 0) return 0; // every count even → all cancel int result = 0; for (int i = 0; i < n; i += 2) { // even indices onlyExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong index parity
For odd n the survivors are the 0-based EVEN indices. XORing odd indices (or assuming 1-based) gives the wrong element set.
Explore the code comparisonHide the code comparison
Wrong index parity
For odd n the survivors are the 0-based EVEN indices. XORing odd indices (or assuming 1-based) gives the wrong element set.
Don't write this
for i in range(1, n, 2): # odd indices — wrong
result ^= arr[i]Write this instead
for i in range(0, n, 2): # even indices
result ^= arr[i]2Missing the even-n shortcut
When n is even every occurrence count is even, so the answer is always 0. Skipping this check risks XORing some indices and returning a nonzero wrong value.
Explore the code comparisonHide the code comparison
Missing the even-n shortcut
When n is even every occurrence count is even, so the answer is always 0. Skipping this check risks XORing some indices and returning a nonzero wrong value.
Don't write this
int result = 0;
for (int i = 0; i < n; i += 2) result ^= arr[i]; // wrong when n even
return result;Write this instead
if (n % 2 == 0) return 0;
int result = 0;
for (int i = 0; i < n; i += 2) result ^= arr[i];
return result;3Recomputing subarray XORs in brute force
If you must brute force, recomputing arr[i..j] from i each time is O(n³). Keep a running XOR to stay at O(n²).
Explore the code comparisonHide the code comparison
Recomputing subarray XORs in brute force
If you must brute force, recomputing arr[i..j] from i each time is O(n³). Keep a running XOR to stay at O(n²).
Don't write this
for i in range(n):
for j in range(i, n):
x = 0
for t in range(i, j + 1): # O(n^3)
x ^= arr[t]
result ^= xWrite this instead
for i in range(n):
running = 0
for j in range(i, n):
running ^= arr[j]
result ^= runningRevise
Carry the pattern into the interview
Pattern to remember
Count each element's occurrences → keep only odd parity
Code pattern to memorize
if n is even: return 0
result = 0
for i in range(0, n, 2): # even indices only
result ^= arr[i]
return resultRules to remember
- 1Element at index i belongs to
(i + 1) · (n − i)subarrays: (i+1) choices of left end ≤ i, (n−i) choices of right end ≥ i. - 2XOR cancels anything appearing an even number of times, so only elements with an ODD occurrence count survive.
- 3
(i + 1)·(n − i)is odd ⇔ both factors odd ⇔ieven ANDnodd. A product is odd only when every factor is odd. - 4Therefore: n even → every count is even → answer 0; n odd → only even indices have odd counts → XOR of even-indexed elements.
- 5Indices are 0-based: 'even index' means positions 0, 2, 4, … — re-check the indexing convention before coding.
Use this pattern when
- Aggregating a commutative/associative op (XOR) over all subarrays
- You can count how many subarrays contain each index and reason about parity
- Cancellation properties (XOR, parity) let occurrences with even count vanish
- Turning an O(n²) enumeration into an O(n) parity argument
Choose another pattern when
- The aggregation op doesn't cancel on repeats (e.g. sum, product) → counting parity won't simplify it
- You need each subarray's value, not the overall fold → you must enumerate
- Subarrays are weighted or filtered → the clean (i+1)(n−i) count breaks
- 1-based indexing assumed without checking → off-by-one on which indices survive
Interview takeaway
Folding XOR over all subarrays reduces to a parity count: each element appears (i+1)(n−i) times, and only odd counts survive. The answer is 0 for even n, and the XOR of even-indexed elements for odd n — O(n), no enumeration.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternContribution counting under cancellation. When folding XOR (or any cancelling op) over all subarrays, count how many subarrays contain each index — (i+1)(n−i) — and keep only odd counts. The answer collapses to XOR of even indices for odd n, and 0 for even n.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Subset XOR SumAnother all-combinations XOR aggregation solved by a counting/contribution argument rather than enumeration.
- Count Triplets With XOR ConditionComing soonPrefix-XOR plus counting — same theme of replacing enumeration with structure.
- Sum vs XORBit-by-bit counting determines the answer directly, like the parity argument here.