Single Number III

medium array bit manipulation

Problem

You are given an integer array nums in which exactly two elements appear once and every other element appears twice. Return the two single elements in any order, in O(n) time and O(1) space.

XOR everything: pairs cancel, leaving xorAll = a ^ b. Any bit set in xorAll is a position where a and b differ — isolate the lowest such bit with xorAll & -xorAll. Partition nums on that bit and XOR each half independently — each half now contains pairs plus one of the singletons.

Inputnums = [1, 2, 1, 3, 2, 5]

Output[3, 5]

nums (comma-separated)

def single_number(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x
    diff = xor_all & -xor_all
    a, b = 0, 0
    for x in nums:
        if x & diff:
            a ^= x
        else:
            b ^= x
    return [a, b]

function singleNumber(nums) {
  let xorAll = 0;
  for (const x of nums) xorAll ^= x;
  const diff = xorAll & -xorAll;
  let a = 0, b = 0;
  for (const x of nums) {
    if (x & diff) a ^= x;
    else b ^= x;
  }
  return [a, b];
}

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int x : nums) xorAll ^= x;
        int diff = xorAll & -xorAll;
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x & diff) != 0) a ^= x;
            else b ^= x;
        }
        return new int[]{ a, b };
    }
}

vector<int> singleNumber(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int diff = xorAll & -xorAll;
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & diff) a ^= x;
        else b ^= x;
    }
    return {a, b};
}

Explanation

Two values appear once and everything else appears twice. If we XOR the whole array, the pairs cancel and we are left with xorAll = a ^ b, the XOR of just the two singletons.

We cannot read a and b directly out of that, but we can split the array into two groups so each singleton lands in a different group. Any bit set in xorAll is a position where a and b differ. We isolate the lowest such bit with diff = xorAll & -xorAll.

Now partition every number by whether it has that diff bit. Numbers equal to a all go one way, numbers equal to b all go the other way, and every duplicate pair stays together in the same group.

So we XOR each group independently: in each group the pairs cancel again, leaving just one singleton. That gives us a from one group and b from the other.

Example: nums = [1,2,1,3,2,5]. XOR of all is 3 ^ 5 = 6 = 110; the lowest differing bit isolates the groups, and XOR-ing each half returns 3 and 5.

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