Single Number
Easy
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
1
Explanation. All numbers except 1 are repeated. 1 is the number that appears only once.
Example 2
Input
[ 4, 1, 2, 1, 2 ]
Output
4
Explanation. All numbers except 4 are repeated. 4 is the number that appears only once.
Example 3
Input
[ 1 ]
Output
1
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
- 9