Single Number III

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

Challenge

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

public class Solution {

    /**

     * @param A : An integer array

     * @return : Two integers

     */

    public List<Integer> singleNumberIII(int[] A) {

        // write your code here

        int t = 0;

        for(int a : A){

            t ^= a;

        }

        int firstDiffBit = t & ~(t-1);

        int k = 0, b = 0;

        for(int a : A){

            if((a & firstDiffBit) == 0){

                k ^= a;

            } else{

                b ^= a;

            }

        }

        List<Integer> result = new ArrayList<Integer>();

        result.add(k);

        result.add(b);

        return result;

    }

}