Single Number

ArrayBit Manipulation

Given a non-empty array of integers where every element appears twice except for one. Find that single number which does not appear twice. 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 appears only once while all the other numbers appear twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In the array [4, 1, 2, 1, 2], the number 4 appears only once while all the other numbers appear twice.

Example 3

Input

[
  1
]

Output

Explanation. In the array [1], the number 1 itself is the single number as it's the only number in the array.

Follow-up: Could this problem be solved using other data structures with possibly more space complexity but maybe easier implementation?

Constraints:

1. The array will not be empty.\n2. Each element in the array appears twice except for one.

Views: 2