Find Unique Number

ArrayBit Manipulation

Given an array of integers where every element appears twice except for one. Write a function that finds the element that only appears once. This element should be returned.

Example 1

Input

[
  2,
  3,
  2,
  4,
  4
]

Output

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

Example 2

Input

[
  7,
  7,
  -1,
  -1,
  0
]

Output

Explanation. 0 is the only number which does not repeat.

Example 3

Input

[
  1,
  1,
  2
]

Output

Explanation. All elements except 2 appear twice. Therefore, 2 is the unique number.

Example 4

Input

[
  -3,
  -3,
  5,
  5,
  99
]

Output

Explanation. 99 is the number that appears once while all others appear twice.

Follow-up: Could you implement a solution with a linear runtime complexity, O(n), and without using extra memory, i.e., O(1) space complexity?

Constraints:

The input array will always have at least one element and only one element appears once whereas each of the other elements appears exactly twice. The array may contain both positive and negative integers.

Views: 3