Pattern this teaches:Bit Manipulation
Single Number
An easy Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 3
- Core for
- 9 roles
The problem
In this array every value appears exactly twice except one value, which appears once. Return that lonely value, using linear time and only a constant amount of extra memory.
Example 1
- Input
- nums = [4,3,4,2,3]
- Output
- 2
- Why
- All numbers appear twice except 2 which appears once.
Example 2
- Input
- nums = [5,5,7,7,9]
- Output
- 9
- Why
- All numbers appear twice except 9 which appears once.
Example 3
- Input
- nums = [1]
- Output
- 1
- Why
- The array has only one element, which is the answer.
Constraints
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element appears twice except for one element which appears only once
How to think about it
Updated 2026-09-29Every bit position behaves like an independent parity toggle. Because pairing identical values flips each bit an even number of times and returns it to zero, running XOR across the entire sequence vaporizes all paired numbers at once. What survives is precisely the lone value that had no partner to cancel it.
Approaches, worst first
Hash map frequency table
time O(n) · space O(n)
Record how often every number appears, then walk the map keys to find the one with count one. Clear and direct, but building a dynamic table wastes linear memory for a property that needs no history.
Sort and compare neighbors
time O(n log n) · space O(1)
Sort the array so matching items sit side-by-side in adjacent pairs, then step by two until an element mismatches its partner. Saves hash memory, but reordering costs O(n log n) and mutates the array.
Single XOR reductionWrite this one
time O(n) · space O(1)
Accumulate every element into an accumulator using bitwise XOR. Identical numbers cancel out regardless of visit order because XOR is both commutative and associative, leaving the unique element in a single pass without extra allocations.
Where people lose marks · 3
- Initializing the XOR accumulator with a non-zero value corrupts the final answer, since zero is the true identity element under XOR.
- Relying on arithmetic sum formulas like 2 * sum(set) - sum(array) can overflow standard fixed-width 32-bit integers if numbers or counts are large.
- Thinking negative integers require separate branch handling; two's complement bitwise XOR cancels negative duplicates just as cleanly as positive ones.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
More Bit Manipulation problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .