Lonely Integer

ArrayBit ManipulationHash Table

Given an array of integers where every element appears twice except for one, find the element that does not appear twice.

Example 1

Input

[
  1
]

Output

Explanation. The array contains just one element, which is the lonely integer.

Example 2

Input

[
  2,
  3,
  2
]

Output

Explanation. 3 appears only once while all other integers appear twice.

Example 3

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. 4 is the only integer that appears once.

Example 4

Input

[
  8,
  1,
  4,
  4,
  1,
  8,
  5
]

Output

Explanation. All integers except 5 appear twice in the array.

Follow-up: Can you implement your solution using a bit manipulation technique to achieve a lower complexity?

Constraints:

The length of the input array will be at least 1 and not more than 1000. Each element in the array will be an integer between 1 and 1000.