Single Number Finder

ArrayBit Manipulation

Given a non-empty array of integers where every element appears twice except for one, find that single one. We need to find the element that appears only once in the array while all other elements appear twice.

Example 1

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. In this array, the number 4 is the only number that appears exactly once.

Example 2

Input

[
  2,
  2,
  1
]

Output

Explanation. The number 1 appears only once, while 2 appears twice.

Example 3

Input

[
  7,
  5,
  5,
  6,
  6
]

Output

Explanation. Every number except 7 has a duplicate in the array.

Follow-up: Can you implement a solution with a linear runtime complexity and without using extra memory?

Constraints:

- You may assume that the input always has exactly one number that appears exactly once.\n- All other numbers in the input will appear exactly twice.\n- The input array will never be empty.

Views: 2