Single Number
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Constraints:
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element appears twice except for one.
Examples:
Input: [2,2,1]
Output: 1
Explanation: The element 1 appears only once, while the element 2 appears twice.
Input: [4,1,2,1,2]
Output: 4
Explanation: The element 4 appears only once, while the elements 1 and 2 appear twice.
Solutions
Bit Manipulation
Time: O(n)Space: O(1)
The XOR operation has the property that a ^ a = 0 and a ^ 0 = a. Therefore, when we XOR all the elements in the array, the elements that appear twice will cancel each other out, and the element that appears only once will remain.
def singleNumber(nums):
result = 0; for num in nums:
result ^= num; return resultFollow-up:
What if the array contains multiple single numbers?
