Single Number

ArrayBit ManipulationHash Table

Given a non-empty array of integers where every element appears twice except for one, find that single one which does not appear twice.\n\nExample:\nInput: [4,1,2,1,2]\nOutput: 4

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. All numbers except 1 are repeated. 1 is the number that appears only once.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. All numbers except 4 are repeated. 4 is the number that appears only once.

Example 3

Input

[
  1
]

Output

Explanation. Only one number in the array, hence it's the answer.

Follow-up: Discuss how using bit manipulation could optimize your solution.

Constraints:

You must implement a solution with a linear runtime complexity and use only constant extra space.

Views: 3