Single Number III
Problem
nums in which exactly two values occur
once and every other value occurs exactly twice. Return the two lonely values
(in any order). Aim for linear time and constant extra space.[1,2,1,3,2,5]Output[3,5][-1,0]Output[-1,0][0,1]Output[1,0]2 ≤ n ≤ 3·104 · -231 ≤ nums[i] ≤ 231-1 · Follow-up: O(n) time, O(1) space.
Try it yourself
class Solution {
public int[] singleNumber(int[] nums) {
}
}
a ^ b (pairs cancel). Any set bit of
a ^ b is a bit where a and b differ — split the
array on that bit and each half becomes the classic “one single number” problem.Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.
Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.
Open the Bit Manipulation guide →Approaches
Brute ForceCount Each Element by Rescanning
O(n2)Space O(1)For every element, scan the whole array and count how many times it appears.
The elements whose count is exactly 1 are the answer; stop once two are
found.
public int[] singleNumber(int[] nums) { int[] res = new int[2]; int found = 0; for (int i = 0; i < nums.length && found < 2; i++) { int count = 0; for (int x : nums) { if (x == nums[i]) count++; } if (count == 1) res[found++] = nums[i]; } return res; }
Constant space and obviously correct, but quadratic time.
BetterHash Map Frequency Count
O(n)Space O(n)One pass builds a value → count map; a pass over the map picks
the two keys with count 1. Hashing replaces the inner rescan with an
O(1) average lookup.
public int[] singleNumber(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) count.merge(num, 1, Integer::sum); int[] res = new int[2]; int idx = 0; for (Map.Entry<Integer, Integer> e : count.entrySet()) { if (e.getValue() == 1) { res[idx++] = e.getKey(); if (idx == 2) break; } } return res; }
Linear time, but O(n) memory violates the follow-up.
OptimalXOR + Partition by Lowest Set Bit
O(n)Space O(1)xor of all numbers equals a ^ b ≠ 0.
xor & -xor isolates its lowest set bit, where a and
b differ. Every duplicate pair lands in the same group, so XOR-ing
each group separately cancels the pairs and leaves a in one,
b in the other.
public int[] singleNumber(int[] nums) { int xor = 0; for (int num : nums) xor ^= num; // xor = a ^ b int diff = xor & -xor; // lowest bit where a and b differ int[] res = new int[2]; for (int num : nums) { if ((num & diff) == 0) res[0] ^= num; else res[1] ^= num; } return res; }
Two passes, no extra memory — meets the follow-up.
xor & -xor is safe even for Integer.MIN_VALUE:
its negation overflows back to itself, which is still its lowest set bit.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count Each Element by Rescanning | O(n2) | O(1) |
| Better | Hash Map Frequency Count | O(n) | O(n) |
| Optimal | XOR + Partition by Lowest Set Bit | O(n) | O(1) |
- Writing
num & diff == 1— the masked value isdiff, not 1; compare with0. - Operator precedence:
==binds tighter than&, so parenthesise(num & diff). - Comparing results order-sensitively — the two numbers may be returned in any order.
- Recall Single Number I (XOR all) first, then ask: how do I separate two survivors?
- Explain why duplicates never split: equal numbers share every bit, including
diff. - Mention
Integer.lowestOneBit(xor)as the readable equivalent ofxor & -xor.