DSA problem
Single Number
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.
The key insight is that the XOR operation has two crucial properties: any number XOR-ed with itself yields 0 (so paired duplicates cancel out), and any number XOR-ed with 0 yields the number itself. Because XOR is also commutative and associative, the order of elements does not matter — XOR-ing every element of the array together leaves only the unique number standing.
Examples
Example 1
Input:
nums = [2,2,1]Output:
1Explanation: The pair of 2s cancels via XOR (2 ^ 2 = 0), and 0 ^ 1 = 1, so the single number is 1.
Example 2
Input:
nums = [4,1,2,1,2]Output:
4Explanation: XOR-ing all elements: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4, since each pair cancels out.
Example 3
Input:
nums = [1]Output:
1Explanation: A single element with no pair is the answer itself.
Constraints
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.