XOR & Subarray Patterns

Imagine you're given an array of 100,000 elements, and you need to answer 100,000 queries of the form: "what's the XOR of elements from index L to R?"

The brute force approach — looping from L to R for each query — would take 10 billion operations. That's O(n × q) and it will NOT pass.

Enter Prefix XOR. The idea is dead simple: precompute aprefix array where prefix[i] stores the XOR of all elements from index 0 to i-1. Then any range query becomes a single XOR operation:

This is the prefix sum of the bit world. Build once in O(n), answer every query in O(1). No loops, no brute force, no drama.

And this isn't just for range queries. Prefix XOR unlocks solutions for counting triplets, XOR of all pairings, subset XOR totals, and the XOR beauty of an array. Let's dive in! 🏊

Let's really understand what a prefix XOR array is and how to use it.

Building the Prefix XOR Array

Given an array arr, we buildprefix where:

prefix[0] = 0  // XOR of zero elements = 0 (identity)
prefix[1] = arr[0]
prefix[2] = arr[0] ^ arr[1]
prefix[3] = arr[0] ^ arr[1] ^ arr[2]
...
prefix[i] = XOR of arr[0] through arr[i-1]

// In code:
function buildPrefix(arr) {
  const prefix = new Array(arr.length + 1);
  prefix[0] = 0;
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] ^ arr[i];
  }
  return prefix;
}

Each step: prefix[i+1] = prefix[i] ^ arr[i]. It's that simple. We're literally just accumulating the XOR as we walk through the array.

The Range Query Formula

Here's where the MAGIC happens. To get XOR of arr[l..r]:

Why does this work?
prefix[r+1] = XOR of arr[0..r]
prefix[l] = XOR of arr[0..l-1]

XORing them: (arr[0] ^ ... ^ arr[r]) ^ (arr[0] ^ ... ^ arr[l-1])
The first l elements appear twice → they cancel! Only arr[l..r] remains. 🎯

Problem: Given an array arr and a list of queries [l, r], return the XOR of each subarrayarr[l..r].

🔍 Real-Time Thinking — What Do I Know?

"I need to answer many range XOR queries. Brute force = O(n) per query, O(n × q) total — too slow. But if I precompute a prefix XOR array where prefix[i] = XOR of arr[0..i-1], then XOR of arr[l..r] = prefix[r+1] ^ prefix[l]. Why? prefix[r+1] has everything from 0 to r. prefix[l] has everything from 0 to l-1. XOR them: elements 0..l-1 appear TWICE and cancel (x^x=0). Only arr[l..r] remains. O(n) preprocessing, O(1) per query!"

🤔 Let's Think About It

If you've never seen prefix XOR, you'd probably write a loop for each query:

Brute Force Approach

function xorQueriesBrute(arr, queries) {
  const result = [];
  for (const [l, r] of queries) {
    let xor = 0;
    for (let i = l; i <= r; i++) xor ^= arr[i];
    result.push(xor);
  }
  return result;
  // Time: O(n × q) — might be up to 10^10 ops!
}

✅ This gives the right answer, but it's SLOW. Forn = 10⁵ and q = 10⁵, this is 10 billion XOR operations. Your interviewer will NOT be impressed. 😅

📋 Edge Cases to Consider

• l = r (single element query): prefix[l+1] ^ prefix[l] = arr[l] ^ 0 = arr[l]. Correct!
• l = 0 (query from start): prefix[r+1] ^ prefix[0] = prefix[r+1] ^ 0 = prefix[r+1]. Correct!
• l > r: Invalid query. Problem guarantees l ≤ r, but if not, the formula would give unexpected results.
• Empty array: prefix = [0]. Any query would be out of bounds — no valid queries for empty array.
• Large n (10⁵): Prefix array of size n+1. O(n) memory. Still fine.

✨ The Prefix XOR Optimal Solution

Build prefix XOR once, then answer every query in O(1):

function xorQueries(arr, queries) {
  // Step 1: Build prefix XOR — O(n)
  const prefix = new Array(arr.length + 1);
  prefix[0] = 0;
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] ^ arr[i];
  }

  // Step 2: Answer each query — O(1) each
  return queries.map(([l, r]) => prefix[r + 1] ^ prefix[l]);
  // Total: O(n + q) — linear in both!
}

📊 Dry Run

Let's trace through arr = [2, 3, 1, 4] with queries:

Problem: Given an array, count the number of triplets(i, j, k) where i < j <= ksuch that XOR[i..j-1] == XOR[j..k].

🤔 The Intuition

This looks complex. Three indices, two subarrays, we need their XOR to be equal. Let's break it down using — you guessed it — prefix XOR!

Let's express both sides using our prefix array:

// XOR[i..j-1] = prefix[j] ^ prefix[i]
// XOR[j..k]   = prefix[k+1] ^ prefix[j]

// They're equal:
prefix[j] ^ prefix[i] = prefix[k+1] ^ prefix[j]

// XOR both sides with prefix[j]:
prefix[i] = prefix[k+1]

// 💡 THE INSIGHT: prefix[i] MUST EQUAL prefix[k+1]!

So the condition XOR[i..j-1] == XOR[j..k] simplifies toprefix[i] == prefix[k+1]. The value of j doesn't matter for the equality — any j between i and k works!

Counting the Triplets

For each pair (i, k) whereprefix[i] == prefix[k+1]:

• The number of valid j positions = k - i (j can be i+1 through k)
• But wait — the problem says i < j <= k, so j ∈ [i+1, k]
• That gives k - i choices for j

Algorithm

function countTriplets(arr) {
  const n = arr.length;
  const prefix = new Array(n + 1);
  prefix[0] = 0;
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] ^ arr[i];
  }

  let count = 0;
  // For every pair (i, k) where i < k
  for (let i = 0; i < n; i++) {
    for (let k = i + 1; k < n; k++) {
      if (prefix[i] === prefix[k + 1]) {
        count += k - i;  // all j between i and k work
      }
    }
  }
  return count;
}

// Time: O(n²), Space: O(n)
// Can be optimized to O(n) using a hash map!

Optimized O(n) Solution

We can do this in a single pass. For each position k, we track how many times we've seen each prefix value before. When we encounterprefix[k+1] again, we add the sum of indices to our count:

function countTripletsOptimized(arr) {
  const n = arr.length;
  let count = 0;
  let xor = 0;
  // Map: prefixValue -> { countSoFar, sumOfIndices }
  const map = new Map();
  map.set(0, { count: 1, sum: 0 });

  for (let k = 0; k < n; k++) {
    xor ^= arr[k];  // this is prefix[k+1]

    const entry = map.get(xor);
    if (entry) {
      // Each previous position i where prefix[i] == xor
      // contributes (k - i) = k * count - sumOfIndices
      count += k * entry.count - entry.sum;
      entry.count++;
      entry.sum += k + 1;  // or just k depending on i indexing
    } else {
      map.set(xor, { count: 1, sum: k + 1 });
    }
  }
  return count;
}

Problem: Given an array, compute the XOR of allnums[i] << 16 | nums[j] pairings... actually, wait. Let me rephrase.

The problem: Given two arrays nums1 andnums2, form a new array where i-thelement of nums1 is paired with every element ofnums2. Compute the XOR of all paired values.

🤔 The Decision: Contribute or Cancel?

For each element, I need to know: "Does this element appear an even or odd number of times in all pairings?" Each element in nums1 is paired with EVERY element of nums2 — that's m times. If m is odd, the element contributes to the final XOR (odd occurrences don't cancel). If m is even, it cancels out. Same logic for nums2 elements: each appears n times. So I only need to XOR nums1 if m is odd, and XOR nums2 if n is odd!

🤔 Understanding the Pattern

Let's start simpler. What if we have ONE array [a, b, c] and we XOR all possible pairs (a,b), (a,c), (b,c)?

// Array: [a, b, c]
// All pairs: (a,b), (a,c), (b,c)

// XOR everything:
(a^b) ^ (a^c) ^ (b^c)
= a^b^a^c^b^c
= (a^a) ^ (b^b) ^ (c^c)
= 0 ^ 0 ^ 0
= 0

// Each element appears (n-1) = 2 times → EVEN → all cancel!

Now what if [a, b, c, d]?

// Array: [a, b, c, d]
// All pairs: (a,b), (a,c), (a,d), (b,c), (b,d), (c,d)

// a appears 3 times, b appears 3 times, etc.
// Each element appears (n-1) = 3 times → ODD → contributes
// Result = a ^ b ^ c ^ d

The General Rule

The Actual Problem: Two Arrays

Now for the real problem: we have nums1 (length n) andnums2 (length m). Every element of nums1 is paired with every element of nums2.

How many times does a particular element appear?

• Each element of nums1 appears in m pairs
• Each element of nums2 appears in n pairs

function xorAllPairings(nums1, nums2) {
  const n = nums1.length;
  const m = nums2.length;
  let result = 0;

  // nums1 elements appear m times each
  if (m % 2 === 1) {  // m is odd → each nums1[i] contributes
    for (const num of nums1) result ^= num;
  }

  // nums2 elements appear n times each
  if (n % 2 === 1) {  // n is odd → each nums2[i] contributes
    for (const num of nums2) result ^= num;
  }

  return result;
}

// Example:
// nums1 = [2, 4], nums2 = [1, 3, 5]
// n=2 (even → nums2 cancel), m=3 (odd → nums1 contribute)
// Result = 2 ^ 4 = 6

Problem: Given an array pref wherepref[i] is the XOR of arr[0..i](note: this is a different definition than our prefix array), reconstruct the original arr.

🤔 The Reverse Operation

This is the inverse of building prefix XOR. If you know how to build it, you know how to reverse it. Let's think:

// Given: pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
// pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]

// XOR both:
// pref[i] ^ pref[i-1] = (arr[0]^...^arr[i]) ^ (arr[0]^...^arr[i-1])
//                      = arr[i]   (everything before cancels!)

// So: arr[i] = pref[i] ^ pref[i-1]

Beautiful! The XOR of consecutive prefix values gives us back the original element. This is the inverse property of XOR at work.

function findOriginalArray(pref) {
  const arr = new Array(pref.length);
  arr[0] = pref[0];  // pref[0] = arr[0]
  for (let i = 1; i < pref.length; i++) {
    arr[i] = pref[i] ^ pref[i - 1];
  }
  return arr;
}

// Example: pref = [5, 7, 2, 3, 8]
// arr[0] = 5
// arr[1] = 7 ^ 5 = 2
// arr[2] = 2 ^ 7 = 5
// arr[3] = 3 ^ 2 = 1
// arr[4] = 8 ^ 3 = 11
// Result: [5, 2, 5, 1, 11]

// Verify: pref[0] = 5 = 5 ✅
// pref[1] = 5 ^ 2 = 7 ✅
// pref[2] = 5 ^ 2 ^ 5 = 2 ✅

Problem: Given an array, find the sum of XOR ofall subsets. For each subset, compute the XOR of its elements, then sum all those XOR values.

🔍 Real-Time Thinking — What Do I Know?

"I need the SUM of XOR of ALL subsets. There are 2ⁿ subsets — brute-forcing is impossible for n > 20. But XOR is bit-independent! For each bit position, I ask: 'How many subsets have this bit set in their XOR?' If cnt elements have this bit set, then exactly half of all 2ⁿ subsets (2ⁿ⁻¹) will have this bit set in their XOR — because the number of ways to pick an odd number from cnt elements is 2^(cnt-1), times 2^(n-cnt) for the rest. So the contribution of this bit is 2ⁿ⁻¹ × 2^b. The total = (OR of all elements) × 2ⁿ⁻¹!"

🤔 Let's Think About This

For an array of size n, there are 2ⁿ subsets. If n is 12 or less, we could brute force. But for n up to 20 or 30, we need a smarter formula.

Key insight: Instead of iterating over subsets, we can think about each bit position independently and count how many subsets have that bit set in their XOR.

Bit Contribution Approach

For bit position b, let's say there arecnt elements with that bit set to 1.

For a subset's XOR to have bit b = 1, the subset must contain an oddnumber of elements with bit b set.

// Number of ways to pick odd number of set-bit elements:
// = (2^(cnt-1))   [combinatorics: half of all subsets have odd count]

// Number of ways to pick any subset of non-set-bit elements:
// = 2^(n-cnt)

// Total subsets with bit b set in XOR:
// = 2^(cnt-1) * 2^(n-cnt) = 2^(n-1)

// So each bit contributes: 2^b * 2^(n-1) = 2^(n-1) * 2^b
// But only if cnt > 0! (If cnt=0, no subset has this bit set)

The Formula

Wait, what? Let me explain. If we compute the OR of all elements, that tells us which bit positions have at least one element with that bit set. Then we multiply by 2^(n-1) because each such bit contributes2^b * 2^(n-1) to the total sum.

function subsetXORSum(nums) {
  let orAll = 0;
  for (const num of nums) orAll |= num;
  return orAll * (1 << (nums.length - 1));
}

// Example: nums = [1, 3]
// OR = 1 | 3 = 3 (binary 11)
// n = 2, 2^(n-1) = 2^1 = 2
// Result = 3 * 2 = 6

// Let's verify with all subsets:
// {} → {} → XOR = 0
// {1} → {1} → XOR = 1
// {3} → {3} → XOR = 3
// {[1, 3]} → {[1, 3]} → XOR = 2
// Sum = 0 + 1 + 3 + 2 = 6 ✅

Dry Run — Why Each Bit Contributes 2^(n-1)

Problem: The XOR beauty of an array is defined as the XOR of(nums[i] | nums[j]) & nums[k] for all triplets(i, j, k) where0 <= i < j < k < n.

🤔 Breaking Down the Problem

This looks INTIMIDATING. Three nested loops? That's O(n³). But XOR gives us a massive shortcut. Let's think bit by bit.

For a fixed bit position b:

• nums[i] | nums[j] has bit b = 1 if at least one of nums[i], nums[j] has bit b = 1
• Then (OR) & nums[k] has bit b = 1 if AND with nums[k] also has bit b = 1
• So the whole expression has bit b = 1 iff: at least one of i,j has bit b AND k has bit b

Counting Contributions

Let cnt = number of elements with bit b = 1.

For a fixed k with bit b = 1:

• We need pairs (i, j) where i < j < k and at least one of them has bit b = 1
• Total pairs before k: C(k, 2)
• Pairs where neither has bit b: C(k - onesBeforeK, 2) where onesBeforeK is count of elements before k with bit b set
• Valid pairs = total pairs - bad pairs

The total count per bit needs to be odd for the bit to contribute (since we're XORing everything). After analysis, the formula simplifies beautifully:

function findXORBeauty(nums) {
  const n = nums.length;
  let result = 0;

  for (let bit = 0; bit < 32; bit++) {
    let count = 0;
    for (const num of nums) {
      if ((num >> bit) & 1) count++;
    }
    if (count >= 2) {
      result |= (1 << bit);
    }
  }
  return result;
}

// Example: nums = [1, 3, 5]
// Bit 0: count = 2 (1, 3, 5 have bit 0 set: 1 has it, 3 has it, 5 has it) → count=3? No...
// 1 = 001 → bit 0 = 1, bit 1 = 0, bit 2 = 0
// 3 = 011 → bit 0 = 1, bit 1 = 1, bit 2 = 0
// 5 = 101 → bit 0 = 1, bit 1 = 0, bit 2 = 1
// Bit 0: count = 3 (all three have it) → ≥ 2 → contributes
// Bit 1: count = 1 (only 3 has it) → &lt; 2 → doesn't contribute
// Bit 2: count = 1 (only 5 has it) → &lt; 2 → doesn't contribute
// Result = 2^0 = 1

Why count ≥ 2?

Intuitively: if only one element has a particular bit set, then in any triplet (i, j, k), the "OR" step can only use that single element for that bit, and the "AND" step needs k to also have it. The combinatorics work out such that the total number of triplets with that bit set is always even — meaning it cancels out in the final XOR.

But if at least two elements have the bit set, the count flips to odd, and the bit contributes.

1. Prefix XOR is the prefix sum of the bit world — build once in O(n), answer range queries in O(1)
2. The formula prefix[r+1] ^ prefix[l] cancels the first l elements, leaving XOR of arr[l..r]
3. Equal XOR subarrays → equal prefix values — for triplet problems, prefix[i] == prefix[k] is the condition to check
4. Pairing patterns — each element participates in (n-1) or (m) pairs; odd count → contributes, even → cancels
5. Reverse prefix XOR — arr[i] = pref[i] ^ pref[i-1] uses XOR's self-inverse property
6. Subset XOR sum — each bit present in any element contributes 2^(n-1) × 2^b; formula = OR of all × 2^(n-1)
7. XOR beauty — for each bit, if count ≥ 2, that bit contributes. No triple loop needed!
8. Think bit-by-bit — most XOR problems decompose into independent per-bit analysis
9. Time: O(n), Space: O(n) for prefix, can often be reduced to O(1) with running XOR
10. Practice! — These patterns click with repetition. Hit the Playground below each problem 🥋