Find Unique Number

ArrayBit ManipulationHash Table

Given an array of integers where every element appears twice except for one, find that unique non-repeated integer. Return the unique integer.

Example 1

Input

[
  2,
  3,
  2,
  4,
  4
]

Output

Explanation. In the array, all elements except 3 appear twice. Therefore, the unique number is 3.

Example 2

Input

[
  7,
  7,
  8
]

Output

Explanation. Here, the number 8 is the only one that appears once.

Example 3

Input

[
  1,
  1,
  2,
  2,
  3,
  3,
  4
]

Output

Explanation. Every number except for 4 appears twice.

Follow-up: Can you solve this problem in linear time and without using extra space for another data structure?

Constraints:

- The array will always have at least one element. - Except for one unique element, all other elements will appear exactly twice.