DSA AnimatorDSA animations
Single Number LC #136 Easy Bit Manipulation · XOR
Problem

Every element of nums appears twice except for one, which appears once. Find that single one, in linear time and using only constant extra space.

Example 1
Input: nums = [4,1,2,1,2]
Output: 4
Example 2
Input: nums = [2,2,1]
Output: 1
Constraints: 1 ≤ nums.length ≤ 3·10⁴  |  each element appears twice except one
🔢 nums
0–255 · up to 15 numbers · every value twice except one
bit = 1 🔄 bit flipped by this XOR 💥 value seen twice: its bits have cancelled⭐ survivor
Variables
x
—
acc
0
pairs cancelled
0
💡 Step Logic
Press ▶ Play or Next to begin.
✓
Ready
0 / 0
Pick an example and press Play.
Algorithm
1
acc = 0 (XOR's "nothing")
2
For every x: acc ^= x 🔄 flips the bits where x has a 1
3
Return acc: pairs have cancelled, the single number is left ⭐
Time
O(n)
Space
O(1)
⊕ XOR truth table
0^0=0
0^1=1
1^0=1
1^1=0

"Different → 1, same → 0". Each bit column of acc is just the parity (odd/even count) of the 1s seen in that column. Paired numbers add an even count, so only the single number's bits stay odd.

⚠️ Edge cases & follow-ups

Works for negative numbers too (the sign bit cancels the same way). A HashSet also works but costs O(n) space, and sorting costs O(n log n). Related: 137 (every other number appears 3×: count bits mod 3) and 260 (two singles: split them by one differing bit).