Find Single Number

ArrayBit ManipulationHash Table

Given a non-empty array of integers where every element appears twice except for one, find that single one. Write a function that outputs the single element.

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. All elements except 1 appear twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. All elements except 4 appear twice.

Example 3

Input

[
  1
]

Output

Explanation. Only one element in the array, that is the single number.

Example 4

Input

[
  -1,
  -1,
  -2
]

Output

-2

Explanation. All elements except -2 appear twice.

Follow-up: Can you implement the solution with a linear runtime complexity and without using extra memory?

Constraints:

The array will always be non-empty and will always have exactly one element that appears only once. Elements can be any integer value, negative or positive.

Views: 3