Single Number Finder

ArrayBit ManipulationHash Table

Given a non-empty array of integers where every element appears twice except for one, find the single element that does not appear twice. The solution should have a linear runtime complexity and use no extra memory.

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. In the array [2, 2, 1], the number '1' appears only once.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In the array [4, 1, 2, 1, 2], the number '4' is the only one that appears exactly once.

Example 3

Input

[
  1
]

Output

Explanation. In the array with a single element [1], the number '1' itself is the only one appearing once.

Follow-up: Can you implement the solution using bit manipulation techniques to achieve the desired complexities?

Constraints:

The input array contains at least one number and at most 30000 numbers. Each number appears exactly twice, except for one which appears exactly once.

Views: 3