XOR Tricks

1. 1.Single Number
   XOR all numbers: x ^ x = 0 and x ^ 0 = x. Unique number remains in O(N) time & O(1) spaceeasy
2. 2.Missing Number
   Expected XOR (0..N) ^ Actual array XOR = Missing numbereasy
3. 3.Find the Difference
   XOR all chars of s and t: extra character remainseasy
4. 4.Hamming Distance
   Count set bits of x ^ y (positions where bits differ)easy
5. 5.Single Number III
   XOR all = a ^ b. Isolate diffBit = xor & -xor to split into 2 groups where duplicates cancel outmedium
6. 6.XOR Queries of a Subarray
   Prefix XOR array: query(L, R) = pref[R+1] ^ pref[L]medium
7. 7.Decode XORed Array
   Reconstruct: arr[i+1] = encoded[i] ^ arr[i]easy
8. 8.Decode XORed Permutation
   Calculate total XOR of 1..N + encoded odds to find first elementmedium
9. 9.Maximum XOR of Two Numbers in an Array
   Bit Trie: insert binary numbers and greedily choose opposite bit from high to lowmedium
10. 10.Maximum XOR With an Element From Array
    Offline queries sorted by limit + Bit Trie insertionhard
11. 11.Count Triplets That Can Form Two Arrays of Equal XOR
    Prefix XOR array: if pref[i] == pref[k+1], all j in between work (k - i triplets)medium
12. 12.XOR Operation in an Array
    Simulate or math formula using n % 4 XOR patterneasy
13. 13.Bitwise XOR of All Pairings
    Parity check: A[i] appears len(B) times, B[j] appears len(A) timesmedium
14. 14.Minimum Bit Flips to Convert Number
    Count set bits of start ^ goaleasy
15. 15.Find XOR Sum of All Pairs Bitwise AND
    Distributive law: (a1 ^ a2) & (b1 ^ b2)hard

1. 16.Single Number II
   Bit counting: For each bit position sum % 3 gives unique bitmedium
2. 17.XOR Beauty of Array
   XOR self-cancellation symmetry reduces problem to XOR of all elementsmedium
3. 18.Neighboring Bitwise XOR
   Total XOR sum of derived array must be 0 for valid original arraymedium
4. 19.Find Original Array From Prefix XOR
   Reconstruct: arr[i] = pref[i] ^ pref[i-1]medium
5. 20.Maximum XOR for Each Query
   Cumulative XOR ^ maxBitMask ((1<<k) - 1)medium
6. 21.Count Pairs With XOR in a Range
   Bit Trie prefix counting for values < highhard
7. 22.XOR of Numbers Appearing Twice
   XOR elements with frequency == 2easy
8. 23.XOR Range Queries
   Prefix XOR array range query calculationmedium
9. 24.Nim Game / XOR Game basics
   Bouton theorem: Nim sum (XOR sum of pile sizes) == 0 means losing positioneasy

How to Think

1. Every value appears twice except one?XOR everything (x ^ x = 0)
2. Need find missing value?Expected XOR ^ Actual XOR = Missing
3. Need know which bits differ?a ^ b (1s mark differing positions)
4. Need split 2 unique numbers?XOR all + Isolate diff bit (diff = xor & -xor)
5. Need maximum XOR?Bit Trie (choose opposite bit from high to low)

// Single Number I: Pairs cancel out in O(N) time & O(1) space
func singleNumber(nums []int) int {
    ans := 0
    for _, num := range nums {
        ans ^= num
    }
    return ans
}

// Single Number III: Find 2 unique numbers using isolated diffBit
func singleNumberIII(nums []int) []int {
    xorSum := 0
    for _, n := range nums {
        xorSum ^= n
    }

    // Isolate rightmost set bit
    diffBit := xorSum & -xorSum

    a, b := 0, 0
    for _, n := range nums {
        if (n & diffBit) == 0 {
            a ^= n // Group A
        } else {
            b ^= n // Group B
        }
    }
    return []int{a, b}
}

Single Number III — Split Using One Differing Bit

Prefix XOR & Subarray Range Queries

// Range XOR from index L to R in O(1) time
func rangeXOR(prefix []int, L int, R int) int {
    return prefix[R+1] ^ prefix[L]
}

x ^ x = 0  and  x ^ 0 = x
a ^ b ^ a = b (Self-cancellation)
Same pair → disappears | Odd count → survives
Expected ^ Actual = Missing Number
Range XOR [L..R] = prefix[R+1] ^ prefix[L]

Common Interview Mistakes

Interview Rules

1. 1. Duplicate pairs + one unique? → XOR all (x ^ x = 0)
2. 2. Missing number 0..N? → Expected XOR (0..N) ^ Actual array XOR
3. 3. Find differing bits? → a ^ b (1s mark differing positions)
4. 4. Hamming distance? → Count set bits of x ^ y
5. 5. Two unique values? → XOR all + Isolate differing bit (diffBit = xor & -xor)
6. 6. Subarray range XOR? → Prefix XOR (rangeXOR = prefix[R+1] ^ prefix[L])
7. 7. Maximum XOR of array pairs? → Bit Trie (choose opposite binary bit high to low)
8. 8. Overall Complexity → O(N) time, O(1) auxiliary space

x ^ x               → 0
x ^ 0               → x
Same pair           → disappears
Odd occurrence      → survives
Different bits      → XOR gives 1
Missing value       → Expected ^ Actual
Two unique          → XOR + split by bit
Range XOR           → Prefix XOR
Maximum XOR         → Bit Trie

💡 Golden Rule: "XOR is cancellation: equal things disappear, and differences remain."