XOR patterns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Single Number: Every element appears twice except for one
public int singleNumber(int[] nums) {
    int unique = 0;
    for (int num : nums) {
        unique ^= num; // Pairs cancel out to 0; remaining is unique
    }
    return unique;
}

// Missing Number in range [0, n]
public int missingNumber(int[] nums) {
    int xor = nums.length;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i]; // Matching indices and values cancel
    }
    return xor;
}

// Single Number III: Exactly two unique numbers in array of pairs
public int[] singleNumberTwoUniques(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n; // xor = a ^ b

    // Find any bit where a and b differ (e.g. lowest set bit)
    int diffBit = xor & (-xor);
    int a = 0, b = 0;

    for (int n : nums) {
        if ((n & diffBit) == 0) a ^= n; // Group 1: bit is 0
        else b ^= n;                   // Group 2: bit is 1
    }
    return new int[]{a, b};
}