Single Number Finder

ArrayBit Manipulation

Given a non-empty array of integers where every element appears twice except for one, find that single one. The algorithm should have a linear runtime complexity. Try to implement it without using extra memory.

Example 1

Input

[
  2,
  2,
  1
]

Output

Explanation. Only the number '1' appears once while '2' appears twice.

Example 2

Input

[
  4,
  1,
  2,
  1,
  2
]

Output

Explanation. Only the number '4' appears once while '1' and '2' each appear twice.

Example 3

Input

[
  1
]

Output

Explanation. Only one element in the array, which is '1'.

Follow-up: Can you propose a method that uses bit manipulation to solve the problem?

Constraints:

1 <= nums.length <= 3 * 104 -3 * 104 <= nums[i] <= 3 * 104 Each element in the array appears twice except for one element which appears only once.

Accepted: 1/1
Acceptance Rate: 100.0%
Views: 3