Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Common XOR Patterns
DSA

Common XOR Patterns

Learn common XOR properties and techniques for solving missing number, duplicate, parity, and related problems.

XOR becomes especially powerful in interview problems because of one important property:

Pairs self-destruct, the loner survives. The classic single-number trick:

Single Number (XOR Cancellation)

Find the element appearing once when every other appears twice.

XOR has a^a=0 and 0^a=a, and it commutes, so pairing off all duplicate values leaves only the loner. One pass, O(n) time, O(1) space — no hash set, no sorting.

ARRAY VISUALIZER
Steps –
4
0
1
1
2
2
1
3
2
4
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        x = 0
                      
                        2
                        for v in nums:
                      
                        3
                          x = x ^ v
                      
                        4
                        return x   // pairs cancelled out

Equal values cancel each other, while different values remain.

Mental Trigger

XOR = same cancels, different survives

Core properties:

a ^ a = 0
a ^ 0 = a
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

These properties make XOR useful for:

  • Finding unique numbers
  • Tracking parity
  • Prefix range queries
  • Subarray XOR problems
  • Splitting values by a differing bit

Pattern Table

PatternTypical QuestionKey Idea
Single numberOne value appears onceCancel pairs
Two unique numbersTwo values appear onceSplit by differing bit
Prefix XORRange XOR queryPrefix cancellation
Subarray XORXOR equals KPrefix XOR + HashMap
Toggle / parityOdd/even stateXOR flips state

1. Generic XOR Template

Everything starts with repeated XOR:

int xor = 0;

for (int num : arr) {
    xor ^= num;
}
xor = 0

for num in arr:
    xor ^= num
int x = 0;

for (int num : arr) {
    x ^= num;
}
let x = 0;

for (const num of arr) {
  x ^= num;
}

Because:

x ^ x = 0
x ^ 0 = x

equal values cancel automatically.

2. Single Number

Problem

Every element appears twice except one element.

Find the element that appears once.

Java Code

public int singleNumber(int[] arr) {
    int xor = 0;

    for (int num : arr) {
        xor ^= num;
    }

    return xor;
}
def single_number(arr):
    xor = 0

    for num in arr:
        xor ^= num

    return xor
int singleNumber(vector<int>& arr) {
    int x = 0;

    for (int num : arr) {
        x ^= num;
    }

    return x;
}
function singleNumber(arr) {
  let x = 0;

  for (const num of arr) {
    x ^= num;
  }

  return x;
}

Example

arr = [4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2

= 4

The pairs disappear:

1 ^ 1 = 0
2 ^ 2 = 0

All pairs + one unique → XOR everything.

3. Two Unique Numbers

Problem

Every element appears twice except two numbers.

Find both unique numbers.

Example:

[1, 2, 1, 3, 2, 5]

Unique → 3, 5

Java Code

public int[] twoSingleNumbers(int[] arr) {
    int xor = 0;

    // XOR of the two unique numbers
    for (int num : arr) {
        xor ^= num;
    }

    // Rightmost bit where the two numbers differ
    int diffBit = xor & -xor;

    int a = 0;
    int b = 0;

    for (int num : arr) {
        if ((num & diffBit) == 0) {
            a ^= num;
        } else {
            b ^= num;
        }
    }

    return new int[]{a, b};
}
def two_single_numbers(arr):
    xor = 0

    # XOR of the two unique numbers
    for num in arr:
        xor ^= num

    # Rightmost bit where the two numbers differ
    diff_bit = xor & -xor

    a = 0
    b = 0

    for num in arr:
        if (num & diff_bit) == 0:
            a ^= num
        else:
            b ^= num

    return [a, b]
vector<int> twoSingleNumbers(vector<int>& arr) {
    int x = 0;

    // XOR of the two unique numbers
    for (int num : arr) {
        x ^= num;
    }

    // Rightmost bit where the two numbers differ
    int diffBit = x & -x;

    int a = 0;
    int b = 0;

    for (int num : arr) {
        if ((num & diffBit) == 0) {
            a ^= num;
        } else {
            b ^= num;
        }
    }

    return {a, b};
}
function twoSingleNumbers(arr) {
  let x = 0;

  // XOR of the two unique numbers
  for (const num of arr) {
    x ^= num;
  }

  // Rightmost bit where the two numbers differ
  const diffBit = x & -x;

  let a = 0;
  let b = 0;

  for (const num of arr) {
    if ((num & diffBit) === 0) {
      a ^= num;
    } else {
      b ^= num;
    }
  }

  return [a, b];
}

How It Works

Suppose:

a = 3  → 011
b = 5  → 101

They differ at some bit.

The XOR:

011
101
---
110

contains the bits where they differ.

We extract one differing bit:

int diffBit = xor & -xor;

Then divide all numbers into two groups.

Group 1 → differing bit = 0
Group 2 → differing bit = 1

Each duplicate pair stays in the same group and cancels.

The two unique numbers end up in different groups.

Two unique numbers → XOR all → find differing bit → split into two groups.

4. Prefix XOR

Prefix XOR is the XOR equivalent of prefix sums.

Define:

prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

Java Code

public int[] buildPrefixXOR(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n];

    prefix[0] = arr[0];

    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] ^ arr[i];
    }

    return prefix;
}
def build_prefix_xor(arr):
    n = len(arr)
    prefix = [0] * n

    prefix[0] = arr[0]

    for i in range(1, n):
        prefix[i] = prefix[i - 1] ^ arr[i]

    return prefix
vector<int> buildPrefixXOR(vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n);

    prefix[0] = arr[0];

    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] ^ arr[i];
    }

    return prefix;
}
function buildPrefixXOR(arr) {
  const n = arr.length;
  const prefix = new Array(n);

  prefix[0] = arr[0];

  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] ^ arr[i];
  }

  return prefix;
}

5. XOR Range Query

Once we have prefix XOR, we can calculate:

arr[l] ^ arr[l+1] ^ ... ^ arr[r]

using:

prefix[r] ^ prefix[l - 1]

Java Code

public int rangeXOR(int[] prefix, int l, int r) {
    if (l == 0) {
        return prefix[r];
    }

    return prefix[r] ^ prefix[l - 1];
}
def range_xor(prefix, l, r):
    if l == 0:
        return prefix[r]

    return prefix[r] ^ prefix[l - 1]
int rangeXOR(vector<int>& prefix, int l, int r) {
    if (l == 0) {
        return prefix[r];
    }

    return prefix[r] ^ prefix[l - 1];
}
function rangeXOR(prefix, l, r) {
  if (l === 0) {
    return prefix[r];
  }

  return prefix[r] ^ prefix[l - 1];
}

Why?

Suppose:

prefix[r] = a ^ b ^ c ^ d
prefix[l-1] = a ^ b

Then:

(a ^ b ^ c ^ d) ^ (a ^ b)

becomes:

c ^ d

because:

a ^ a = 0
b ^ b = 0

Prefix XOR = fast range cancellation.

6. Subarray XOR = K

This is one of the most important XOR interview patterns.

Problem

Count how many subarrays have XOR equal to k.

Java Code

public int countSubarraysWithXOR(int[] arr, int k) {
    Map<Integer, Integer> freq = new HashMap<>();

    int xor = 0;
    int count = 0;

    // Empty prefix
    freq.put(0, 1);

    for (int num : arr) {
        xor ^= num;

        int target = xor ^ k;

        count += freq.getOrDefault(target, 0);

        freq.put(xor, freq.getOrDefault(xor, 0) + 1);
    }

    return count;
}
def count_subarrays_with_xor(arr, k):
    freq = {}

    xor = 0
    count = 0

    # Empty prefix
    freq[0] = 1

    for num in arr:
        xor ^= num

        target = xor ^ k

        count += freq.get(target, 0)

        freq[xor] = freq.get(xor, 0) + 1

    return count
int countSubarraysWithXOR(vector<int>& arr, int k) {
    unordered_map<int, int> freq;

    int x = 0;
    int count = 0;

    // Empty prefix
    freq[0] = 1;

    for (int num : arr) {
        x ^= num;

        int target = x ^ k;

        count += freq[target];

        freq[x]++;
    }

    return count;
}
function countSubarraysWithXOR(arr, k) {
  const freq = new Map();

  let x = 0;
  let count = 0;

  // Empty prefix
  freq.set(0, 1);

  for (const num of arr) {
    x ^= num;

    const target = x ^ k;

    count += freq.get(target) || 0;

    freq.set(x, (freq.get(x) || 0) + 1);
  }

  return count;
}

Core Equation

For a subarray:

prefix[r] ^ prefix[l - 1] = k

Rearrange:

prefix[l - 1] = prefix[r] ^ k

So for every current prefix XOR:

int target = xor ^ k;

we ask:

Have we seen this target prefix XOR before?

The HashMap stores how many times each prefix XOR has occurred.

Why freq.put(0, 1)?

This represents the empty prefix before the array starts.

Without it, subarrays beginning at index 0 would be missed.

Subarray XOR = Prefix XOR + HashMap.

7. XOR Toggle / Parity

XOR is useful when we only care whether something happened an odd or even number of times.

Java Code

public int toggleBit(int mask, int i) {
    return mask ^ (1 << i);
}
def toggle_bit(mask, i):
    return mask ^ (1 << i)
int toggleBit(int mask, int i) {
    return mask ^ (1 << i);
}
function toggleBit(mask, i) {
  return mask ^ (1 << i);
}

Behavior:

0 ^ 1 = 1
1 ^ 1 = 0

Therefore:

first occurrence  → ON
second occurrence → OFF
third occurrence  → ON
fourth occurrence → OFF

Character Parity Example

public int oddFrequencyMask(String s) {
    int mask = 0;

    for (char c : s.toCharArray()) {
        mask ^= 1 << (c - 'a');
    }

    return mask;
}
def odd_frequency_mask(s):
    mask = 0

    for c in s:
        mask ^= 1 << (ord(c) - ord('a'))

    return mask
int oddFrequencyMask(string s) {
    int mask = 0;

    for (char c : s) {
        mask ^= 1 << (c - 'a');
    }

    return mask;
}
function oddFrequencyMask(s) {
  let mask = 0;

  for (const c of s) {
    mask ^= 1 << (c.charCodeAt(0) - 97);
  }

  return mask;
}

Each set bit represents a character with an odd frequency.

XOR naturally tracks odd/even parity.

8. XOR Swap

XOR can technically swap two integers without a temporary variable.

a = a ^ b;
b = a ^ b;
a = a ^ b;

Example:

a = 5
b = 7

After the three operations:

a = 7
b = 5

Important

This is mainly a conceptual XOR trick.

In production Java code, prefer:

int temp = a;
a = b;
b = temp;

because it is clearer and avoids problems when a and b refer to the same storage location.

XOR is reversible: applying the same XOR operation twice restores the original value.

Pattern Evolution

Basic XOR
    ↓
Same values cancel
    ↓
Single Number
    ↓
Two Unique Numbers
    ↓
Split by Differing Bit
    ↓
Prefix XOR
    ↓
Range XOR
    ↓
Prefix XOR + HashMap
    ↓
Subarray XOR = K

Visual Intuition

XOR works bit by bit:

ABA ^ B
000
011
101
110

The important row is:

1 ^ 1 = 0

That’s the cancellation behavior that powers most XOR tricks.

Common Mistakes

1. Assuming XOR removes every duplicate

XOR cancellation works directly when values occur in pairs.

For example:

[2, 3, 2]

works.

But:

[2, 2, 2, 3]

does not simply identify 3 using the same assumption.

Always check the frequency constraints.

2. Forgetting the empty prefix

For subarray XOR:

freq.put(0, 1);

is essential.

3. Confusing XOR and OR

OR

1 | 1 = 1

OR accumulates/set bits.

XOR

1 ^ 1 = 0

XOR cancels/toggles bits.

4. Forgetting the rightmost set-bit trick

For two unique numbers:

int diffBit = xor & -xor;

This isolates a bit where the two unique numbers differ.

5. Using XOR for normal swapping

Although:

a ^= b;
b ^= a;
a ^= b;

works in many cases, a temporary variable is usually clearer and safer in normal Java code.

Recognition Cheat Sheet

If you see…Think…
All pairs except oneXOR
Two unique numbersXOR + split bit
Odd/even occurrenceXOR
Range XORPrefix XOR
Subarray XOR = KPrefix XOR + HashMap
Toggle stateXOR
Differing bitxor & -xor

Complexity

Single Number

Time:  O(n)
Space: O(1)

Two Unique Numbers

Time:  O(n)
Space: O(1)

Prefix XOR

Build: O(n)
Query: O(1)
Space: O(n)

Subarray XOR = K

Time:  O(n)
Space: O(n)

My Private Notes

Notes are auto-saved locally to this device.