Single Number Finder

ArrayBit ManipulationHash Table

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

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. Here, 1 appears only once while all other elements appear twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. 4 appears only once while all other elements appear twice.

Example 3

Input

[
  1
]

Output

Explanation. 1 appears only once and is the only element.

Follow-up: Can you solve the problem using bit manipulation techniques?

Constraints:

You must implement a solution with a linear runtime complexity and without using extra memory.