LeetCode #260 Single Number III

Medium

Problem

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution

Because all numbers that appears twice can be eliminated by using XOR operator, the difficulty is how can we separate those targets from the mixed XOR value.

The ability of XOR operator is to eliminate the same bit and save the different one. So let’s consider a point of view: if we can get a bit who is equal to 1, we can separate all elements to two parts by comparing them with this bit. And the problem will be reduced to two Single Number problems.

Fortunately, we know how to get the lowest bit by learning how to construct a binary indexed tree.

Complexity

It’s clear that we iterate this list twice so it takes O(2n) = O(n) time with only O(1) extra space.