Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

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

public int singleNumber_1(int[] nums) {
    int ret = 0;
    for (int i = 0; i < nums.length; i++) {
        ret = ret ^ nums[i];
    }
    return ret;
}

Given an array of integers, every element appears three times except for one. Find that single one.

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

public int singleNumber(int[] A) {
    int x1 = 0, x2 = 0;
    int mask;
    for (int i : A) {
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & x2);
        x2 &= mask;
        x1 &= mask;
    }
    return x1; // x1 for one time, x2 for two times
}

public int singleNumber_2(int[] nums) {
    int ret = 0;
    int[] bitnum = new int[32];
    for (int i = 0; i < bitnum.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            bitnum[i] += (nums[j] >> i) & 1;
        }
        ret |= (bitnum[i] % 3) << i;
    }
    return ret;
}

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.

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

public int[] singleNumberIII(int[] nums) {
    int xor = 0, x1 = 0, x2 = 0;
    for (int i : nums) {
        xor ^= i;
    }
    int lastBit = xor - (xor & (xor - 1));
    for (int i : nums) {
        if ((i & lastBit) == 0) {
            x1 ^= i;
        } else {
            x2 ^= i;
        }
    }
    return new int[]{x1, x2};
}