Single Number Finder

ArrayBit ManipulationHash Table

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

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. In the array, 2 appears twice and 1 appears once, so the output is 1.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In the array, 1 and 2 appear twice each and 4 appears once, so the output is 4.

Example 3

Input

[
  1
]

Output

Explanation. The array contains only one element, and since it does not repeat, the output is 1.

Follow-up: Can the problem be extended to detect single elements in an array where every other element appears thrice?

Constraints:

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