Find the Missing Element

ArrayBit ManipulationMath

Given an array of unique integers where each number except one is repeated twice, find the number that does not repeat.

Example 1

Input

[
  2,
  3,
  5,
  2,
  3
]

Output

Explanation. Every number except '5' is repeated. Therefore, the output is 5.

Example 2

Input

[
  7,
  1,
  7,
  8,
  1,
  9,
  9
]

Output

Explanation. 7, 1, and 9 repeat twice whereas '8' does not repeat. Hence, the output is 8.

Example 3

Input

[
  6,
  6
]

Output

Invalid input

Explanation. Input contains all numbers repeated which is not suitable as per constraints.

Follow-up: Can you improve your solution to use O(1) additional space?

Constraints:

The input array will consist of integers and will contain at least three elements. All integers except one will occur exactly twice.