Single number I & II &III

Single Number

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

Bitwise operations.

Single number I
Using XOR operation. Because each number appears twice, XOR cancels out them except the single number.

public class SingleNumber {
    public int singleNumber(int[] A) {
        int rst = 0;
        for (int i = 0; i < A.length; i++)
            //XOR
            rst ^= A[i];
        return rst;
        
    }
}

Single Number II

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

Count each of the 32 bit of every element. Then mod each bit by 3, this operation will cancels out all numbers that appear three times.

Update: 2015 - 01 - 03

I put the array iteration at the outer loop at first, then I realize it will need an extra iteration to do the mod and add bits back.
Loop the bits first allows us to get the result in one pass.

public class Solution {
    public int singleNumber(int[] A) {
        if (A == null || A.length == 0)
            return -1;
        //unsigned int, 32 bits
        int[] bits = new int[32];
        int rst = 0;
        for (int i = 0; i < 32; i++)
        {
            for (int j = 0; j < A.length; j++)
            {
                // & 1 will count only the bit 1
                bits[i] += A[j] >> i & 1;
                bits[i] %= 3;
            }
            //adding back to the original position by left shift i bits. 
            //e.g.  000 = 000 || (1 << 2) = 100
            rst |= (bits[i] << i);
        }
        return rst;
        
    }
}

Single Number III

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:

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?

Similar to the first problem, we use xor. Now after the first traversal, we have a number n that is the xor of the two single numbers. We then try to find the first different bit from the number. Then we traverse the array again, now we xor all numbers with that bit equals 1, for all numbers that appear twice, they will be cancel out. This operation will also cancel one of the two single numbers with that bit equals 1. Now the rest of n is the first number and we use xor to find the second number.

    public int[] singleNumber(int[] nums) {
        int[] rst = new int[2];
        if (nums == null || nums.length < 2)
            return rst;
        int xor = 0;
        for (int n : nums) 
            xor ^= n;
        
        int first_different_bit = 0;
        for (first_different_bit = 0; first_different_bit < 32; first_different_bit++) {
            if (((xor >> first_different_bit) & 1) == 1)
                break;
        }
        
        int num1 = 0;
        for (int n : nums) {
            if (((n >> first_different_bit) & 1) == 1)
                num1 ^= n;
        }
        rst[0] = num1;
        rst[1] = xor ^ num1;
        return rst;
    }