Single Number Finder

ArrayBit Manipulation

Given an array of integers where every element appears twice except for one, find that single number which does not appear twice. You must have a solution with a linear runtime complexity and use only constant extra space.

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. In the array `[2,2,1]`, `2` appears twice and `1` appears once.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. Here, `1` and `2` appear twice, while `4` appears once.

Example 3

Input

[
  1
]

Output

Explanation. Only one element in the array and it appears once.

Follow-up: Can your solution handle a case where numbers can appear twice but one number appears once or three times?

Constraints:

1. The length of the array will be in the range `[1, 10^5]`.\n2. Every element appears twice except for one.

Views: 2