Description
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.
Examples
Input:
nums = [2,2,1]Output:
1Explanation:
The two 2s cancel out with XOR, leaving 1.
Input:
nums = [4,1,2,1,2]Output:
4Explanation:
XORing all elements: 4 XOR 1 XOR 2 XOR 1 XOR 2 = 4 XOR 0 XOR 0 = 4. The paired elements cancel out, leaving the single number.
Input:
nums = [1]Output:
1Explanation:
With only one element in the array, there are no pairs to cancel. XORing just 1 gives 1, which is trivially the single number.
Constraints
- •
1 ≤ nums.length ≤ 3 × 10⁴ - •
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴ - •
Each element in the array appears twice except for one element which appears only once.