Bit tricks let you replace whole data structures with a single integer. XOR is the classic: it is its own inverse, so pairs of equal numbers cancel out.
Given a non-empty list of integers nums in which every element appears exactly twice except for one element that appears once, return that single element.
Examples
Input: nums = [2, 2, 1]
Output: 1
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Input: nums = [1]
Output: 1
Constraints
1 <= len(nums) <= 3 * 10**4- Every element appears twice except one, which appears once
- Target: O(n) time and O(1) extra space (a
Counterworks but is not the point)
Goals
- Use the properties of XOR (x ^ x == 0, x ^ 0 == x) to cancel out pairs
- Solve a counting problem in O(1) extra space instead of with a hash map