1
XOR all
Time O(n) Space O(1)Fold the array with ^.
class Solution {
public int singleNumber(int[] nums) {
int x = 0;
for (int v : nums) x ^= v;
return x;
}
}Verdict: A hash set works but uses O(n) memory.
Problem 34.1 · Bit ManipulationEasy
Single Number
What it teaches: XOR cancels pairs in O(1) space.
Practise it on judges as “Single Number”.
The problem
Every element appears twice except one. Find it in O(n) time and O(1) extra space.
Example 1
Input: nums = [4, 1, 2, 1, 2] Output: 4
Constraints
- 1 ≤ n ≤ 3 × 10⁴
Pattern clues in the wording
- → Everything paired except one
- → O(1) space
These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.
Stuck? Take one hint at a time
class Solution {
public int singleNumber(int[] nums) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | nums = [2,2,1] | 1 |
| 2 | nums = [4,1,2,1,2] | 4 |
+ 1 hidden test the code runner will check
From slow to fast
Approaches
Before you submit
Edge cases and common mistakes
Test these inputs
- Single element
- Negative numbers
Mistakes people make
- Summing and subtracting (overflow risk, and needs extra work).
Interview
Follow-up questions
What if every other element appears three times?