0136 - Single Number

0136 - Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Examples

Input: nums = [2,2,1] Output: 1

Input: nums = [4,1,2,1,2] Output: 4

Input: nums = [1] Output: 1

Constraints

1 <= nums.length <= 3 * 104 -3 * 104 <= nums[i] <= 3 * 104 Each element in the array appears twice except for one element which appears only once.

Java Solution

Bit Manipulation

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}