Leetcode and Lintcode

Single Number III

Problem:

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Have you met this question in a real interview? Yes

Example
Given [1,2,2,3,4,4,5,3] return 1 and 5

Note:

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

Challenge
O(n) time, O(1) extra space.

Leetcode link
Lintcode link

Solution:

This problem is also about bit operation.
First we xor all the numbers in the array.
Then we can get the last digits which equals 1.
The bit represent the last different bit of the two exceptional numbers.
Next, we use the bit to separate the numbers in the array into two group, and use xor to link the numbers in each group.
After the iteration stop, each number left in each group should be the two results.

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
/*************************************************************************
	> File Name: SingleNumberIII.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Mon 16 Nov 11:04:57 2015
 ************************************************************************/

public class SingleNumberIII{
    public int[] singleNumber(int[] nums){
        int[] result = new int[2];
        int temp = 0;
        for (int i = 0; i < nums.length; i++){
            temp ^= nums[i];
        }        
                 
        int lastBit = temp - (temp & (temp - 1));
                 
        for (int i = 0; i < nums.length; i++){
            if ((nums[i] & lastBit) == 0){
               result[0] ^= nums[i] ; 
            } else { 
               result[1] ^= nums[i] ; 
            }    
        }        
                 
        return result;
    }
}