Single Number

ArrayBit ManipulationHash Table

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

Example:

Input: [4, 1, 2, 1, 2]

Output: 4

In this example, every number except 4 comes twice, and 4 is the only number that appears once.

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. In this input, the number `1` is the only element that appears exactly once.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In this input, the number `4` is the only element that appears exactly once.

Example 3

Input

[
  1
]

Output

Explanation. With only one element in the input, that element is the single number.

Follow-up: How would you handle the case, if the array becomes significantly large or contains all elements very multiple times except one element which appears only once?

Constraints:

The length of the input array is always at least 1 and contains only integers. Each element appears exactly twice except for one element which appears exactly once.

Views: 3