Single Number

ArrayBit ManipulationHash Table

Given a non-empty array of integers where every element appears twice except for one, find that single one that does not appear twice.

Write a function singleNumber that takes this array as input and returns the element that appears only once.

Example 1

Input

Output

Explanation. All the elements appear twice except for 1 which appears only once.

Example 2

Input

Output

Explanation. All the elements appear twice except for 4 which appears only once.

Example 3

Input

[
  [
    1
  ]
]

Output

Explanation. With only one element, 1 is the single number.

Follow-up: Can this problem be solved using bit manipulation techniques? If so, how would that implementation differ in terms of readability and performance?

Constraints:

1. You may assume that every number appears exactly twice, except for one number which appears only once. 2. The array will contain at least one element. 3. The solution should run in linear time complexity and use only constant extra space.

Views: 2