Single Number

SingleNumber.java

/**
  Given an array of integers, every element appears twice except for one. Find that single one.
  Note:
  Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
*/

public class Solution{
    public int singleNumber(int[] A){
    int num = A[0];
    for(int i = 1; i < A.length; i++){
        num ^= A[i];
    }
    return num;
  }
}

SingleNumberII.java

/**
 * Given an array of integers, every element appears three times except for one. Find that single one.
 * Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
 */
 
 public class Solution {
    public static int singleNumber(int[] A) {
		int one = 0, two = 0;
		int n = A.length;
		for (int i = 0; i < n; i++) {
			int one_ = (one ^ A[i]) & ~two;
			int two_ = A[i] & one | ~A[i] & two;
			one = one_;
			two = two_;
		}

		return one;
	}

	public int singleNumberII(int[] A) {
		int N = A.length;
		if (N == 0) {
			return N;
		}

		int[] counts = new int[32];
		int result = 0;
		for (int i = 0; i < 32; i++) {
			for (int j = 0; j < N; j++) {
				if (((A[j] >> i) & 1) == 1) {
					counts[i] = (counts[i] + 1) % 3;
				}
			}
			result |= (counts[i] << i);
		}

		return result;
	}
}

SingleNumberIII.java

/**
 * 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?
 */
 
public class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for(int num : nums)  diff ^= num;
        diff = Integer.highestOneBit(diff);
        int[] res = new int[2];
        Arrays.fill(res, 0);
        for(int num : nums) {
            if((diff & num) == 0)  res[0] ^= num;
            else res[1] ^= num;
        }
        return res;
    }
}