Single Number Finder

ArrayBit ManipulationHash Table

Given a non-empty array of integers, 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

[
  2,
  2,
  1
]

Output

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

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. Here '4' is the single element that does not have a pair.

Example 3

Input

[
  1
]

Output

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

Follow-up: Can you propose how your solution might be adapted if every element appears three times except for one which appears exactly once?

Constraints:

1. The array will contain at least one number. 2. Each element in the array except one will appear exactly twice. 3. The input array may contain both positive and negative integers.

Views: 2