Find Unique Number

easy

Given an array of integers where every integer occurs twice except for one integer, which occurs only once, find and return the unique integer.

Example 1

Input

[
  2,
  3,
  2
]

Output

Explanation. The number 3 occurs only once while all others occur twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. The number 4 occurs only once while all others occur twice.

Example 3

Input

[
  7
]

Output

Explanation. The number 7 is the only number and thus it is unique.

Follow-up: Can you implement this function with a linear runtime complexity and without using extra space for another data structure?

Constraints:

The input array will have at least one element and always contain a single unique element. The array will contain no more than 10^5 integers.