Single Number Finder

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\nNote: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. All numbers except 1 appears twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. All numbers except 4 appear twice.

Example 3

Input

[
  1,
  1,
  2,
  2,
  3,
  3,
  5
]

Output

Explanation. All numbers except 5 appear twice.

Follow-up: Can the solution be extended to work on arrays where every element appears three times except for one appearing once?

Constraints:

1. The input array will not be empty.\n2. Except for one integer, every other integer will appear exactly twice in the list.

Views: 3