Single Number III

Posted on | In | |

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.

For example:

  • Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

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

Idea

Suppose C = A ^ B, then the 1 bits in C are exactly the ones that only exist in either A or B (C cannot be 0 or A and B would be the same). It is because all other elements appearing twice are turned into 0 during the XOR process. The XOR result C is actually the XOR of the only two elements each appearing once.

Thus, for whichever 1 bit in C, having it or not can be the condition for dividing those elements into Group A(which containing A) and Group B (which containing B). As per to the explanation above, the XOR result of those elements in Group A (except for A) would be 0, and the XOR of all elements in Group A would be A. It’s the same story in Group B.

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int[] singleNumber(int[] nums) {
        int c = 0;
        for (int num : nums) {
            c ^= num;
        }
        // get the lowest "1" bit of C
        c &= -c;
        // rets[0], rets[1] would be the XOR results of Group A and Group B
        int[] rets = new int[2];
        for (int num : nums) {
            if ((num & c) == 0) {
                rets[0] ^= num;
            }
            else {
                rets[1] ^= num;
            }
        }
        return rets;
    }
}
  • Trick of getting the lowest 1 bit of C
    – For a positive integer C, -C would be stored as 2's complement of C and with the highest bit (sign bit) set to 1. To compute the 2's complement of an integer, simply keep the trailing 0s and the lowest 1 bit unchanged, and then revert all the higher bits. So, C & (-C) would be the lowest 1 bit of C.