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. You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In this array, every element except for '4' appears exactly twice. Thus, the result is 4.

Example 2

Input

[
  2,
  2,
  1
]

Output

Explanation. Here, '2' appears twice, and '1' appears only once, making 1 the single element.

Example 3

Input

[
  1
]

Output

Explanation. With only one element, '1' is obviously the single element.

Follow-up: Can this problem be solved using bit manipulation? Discuss possible approaches.

Constraints:

1. The input array will not be empty.\n2. All elements appear twice except one.

Views: 4