Find the Two Non-Repeating Numbers
A medium Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 2
- Core for
- 9 roles
The problem
Given an integer array where exactly two elements appear only once and all other elements appear exactly twice, find the two elements that appear only once. The order of the answer does not matter.
Example 1
- Input
- nums = [1, 2, 1, 3, 2, 5]
- Output
- [3, 5]
- Why
- 1 appears twice, 2 appears twice, 3 appears once, and 5 appears once. The two unique elements are 3 and 5.
Example 2
- Input
- nums = [-1, 0]
- Output
- [-1, 0]
- Why
- Both -1 and 0 appear exactly once.
Example 3
- Input
- nums = [0, 1]
- Output
- [0, 1] or [1, 0]
- Why
- Both 0 and 1 appear exactly once.
Constraints
- 2 <= nums.length <= 3 * 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- Each integer in nums appears twice except for exactly two integers which appear once
How to think about it
Updated 2026-09-09XORing every element cancels duplicates and yields a ^ b, the XOR sum of the two distinct uniques. Because a and b differ, at least one bit in a ^ b must be set to one. That bit serves as a universal discriminator: every number in the entire array can be categorized into two isolated groups based on whether that bit is present, putting a and b into separate buckets.
Approaches, worst first
Hash map frequency tally
time O(n) · space O(n)
Record occurrences of each integer in a hash map, then collect keys with frequency one. Simple, but consumes linear auxiliary memory on large inputs.
Sort and adjacent comparison
time O(n log n) · space O(1)
Sort the array to cluster identical values together, then scan to identify singletons. Avoids hash overhead, but runs in O(n log n) time and mutates the array.
Partition by differentiating bitWrite this one
time O(n) · space O(1)
Compute the total XOR sum xorSum = a ^ b. Extract any set bit mask using diff = xorSum & (-xorSum). Pass through the array once more, accumulating into two independent buckets based on (num & diff). Duplicates land together and cancel within their bucket, leaving a and b.
Where people lose marks · 2
- In languages with 32-bit signed integers, taking `-xorSum` when xorSum equals -2^31 triggers integer overflow; using unsigned bitwise types or `xorSum & (xorSum - 1) ^ xorSum` avoids undefined behavior.
- Testing `(num & diff) == 1` instead of `(num & diff) != 0`; the isolated bit mask diff is generally greater than one, so masking produces powers of two rather than one.
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 .