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.
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}Follow-up:
What if the array contains multiple single numbers?
