#### Single Number I

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?

**Python (v1)**

*Time complexity: O(N)*

* Space complexity: O(1)*

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ xor = 0 for n in nums: xor ^= n return xor

**Python (v2)**

*Time complexity: O(N)*

*Space complexity: O(1)*

from functools import reduce class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ xor = reduce((lambda x, y: x ^ y), nums) return xor

#### Single Number II

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

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

**Java (extra memory)**

*Time complexity: O(N)*

*Space complexity: O(1)*

public class Solution { public int singleNumber(int[] A) { // write your code here if (A.length == 1){ return A[0]; } int[] bitCount = new int[32]; for (int a : A){ for (int i = 0; i < 32; ++i){ boolean isSet = (a & (1 << i)) != 0; if (isSet){ bitCount[i] = (bitCount[i] + 1) % 3; } } } int res = 0; for (int i = 31; i >= 0; --i){ res |= bitCount[i] << i; } return res; } }

**Java**

*Time complexity: O(N)*

*Space complexity: O(1)*

public class Solution { public int singleNumber(int[] A) { // write your code here int ones = 0; int twos = 0; for (int i = 0; i < nums.length; ++i){ ones = (ones ^ nums[i]) & ~twos; twos = (twos ^ nums[i]) & ~ones; } return ones; } }

**Java (extended to 4 times case)**

*Time complexity: O(N)*

*Space complexity: O(1)*

public class Solution { public int singleNumber(int[] A) { int ones = 0; int twos = 0; for (int i = 0; i < nums.length; ++i){ ones = (ones ^ nums[i]) & ~(twos & ones); twos = (twos ^ nums[i]) & ~ones & ~(twos & ones); } return ones; } }

#### 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**:

- The order of the result is not important. So in the above example,
`[5, 3]`

is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

**Java**

*Time complexity: O(N)*

*Space complexity: O(1)*

public class Solution { public int[] singleNumber(int[] nums) { // write your code here int[] res = new int[2]; if (nums == null || nums.length == 0){ return res; } int diff = 0; for (int n : nums){ diff ^= n; } diff &= ~(diff - 1); for (int n : nums){ if ((n & diff) != 0){ res[0] ^= n; } else { res[1] ^= n; } } return res; } }