What signals in a problem statement indicate the XOR cancellation sub-pattern?

"appears twice except one" / "exactly two elements appear once"; "appears three times except one" (per-bit count mod 3); "encoded[i] = arr[i] XOR arr[i + 1]", decode / recover the array; O(1) extra space with values that are not 0..n

XOR cancellation (Bit Manipulation Sub-pattern)

Q: What makes XOR cancellation different from other sub-patterns?

Twice → XOR everything. Two singles → XOR gives `a ^ b`; split the array by **one bit where a and b differ**. Three times → XOR fails; **count each bit mod 3**. Decoding → XOR the known neighbour back out.

Values that appear an even number of times cancel under XOR, leaving the odd one out. XOR also undoes itself: if c = a ^ b then a = c ^ b.

Signals in the problem statement

›
"appears twice except one" / "exactly two elements appear once"
›
"appears three times except one" (per-bit count mod 3)
›
"encoded[i] = arr[i] XOR arr[i + 1]", decode / recover the array
›
O(1) extra space with values that are not 0..n

What makes it different

Twice → XOR everything. Two singles → XOR gives a ^ b; split the array by one bit where a and b differ. Three times → XOR fails; count each bit mod 3. Decoding → XOR the known neighbour back out.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Single Number
Basic Anchor·LeetCode #136
WalkthroughEasy
2
Decode XORed Array
Basic Reinforcement·LeetCode #1720
WalkthroughEasy
3
Single Number III
Slight Variation·LeetCode #260
WalkthroughMedium
4
Single Number II
Medium·LeetCode #137
WalkthroughMedium

Template

xor-template.cpp

// Every value appears twice except one: pairs cancel (x ^ x = 0, x ^ 0 = x).
int singleOfPairs(const vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

// Exactly two values appear once: XOR of all = a ^ b, which is non-zero.
// Any 1-bit of it differs between a and b; split the array by that bit.
vector<int> twoSingles(const vector<int>& a) {
    unsigned all = 0;
    for (int v : a) all ^= v;
    unsigned low = all & -all;               // lowest 1-bit (unsigned: safe for INT_MIN)
    int g0 = 0, g1 = 0;
    for (int v : a) ((unsigned)v & low ? g1 : g0) ^= v;   // each pair lands in one group
    return {g0, g1};
}

// Every value appears k times except one: count each bit mod k.
int singleOfK(const vector<int>& a, int k) {
    unsigned res = 0;
    for (int b = 0; b < 32; b++) {
        int cnt = 0;
        for (int v : a) cnt += ((unsigned)v >> b) & 1;
        if (cnt % k) res |= 1u << b;         // 1u: bit 31 must not overflow int
    }
    return (int)res;
}

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Bit Manipulation overview Bit counting / powers