Find the Unique Number

ArrayBit ManipulationHash Table

Given an array of integers where every element appears twice except for one unique element, find that single element that does not appear twice. The order of numbers in the input array can be random.

Example 1

Input

[
  2,
  3,
  4,
  3,
  2
]

Output

Explanation. The number 4 is unique in the list as it appears only once.

Example 2

Input

[
  1
]

Output

Explanation. The number 1 is unique as it's the only element.

Example 3

Input

[
  0,
  1,
  0
]

Output

Explanation. Among the values, the number 0 is repeated, and 1 appears only once.

Follow-up: Can you implement your solution without using extra memory, i.e., in constant space complexity?

Constraints:

The input array will contain at least one element and a maximum of 10,000 elements. All integers will be within the 32-bit signed integer range.

Views: 3