#260 Single Number III

frequently reported atAmazon Google

the problem

In plain words

Exactly two elements appear once and all others appear exactly twice. Return the two single elements in any order, using linear time and constant extra space.

in nums = [1,2,1,3,2,5]

out [3,5]

[5,3] is also accepted.

in nums = [-1,0]

out [-1,0]

in nums = [0,1]

out [1,0]

2 ≤ nums.length ≤ 3·10⁴
−2³¹ ≤ nums[i] ≤ 2³¹ − 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternXOR cancellation Bit tricks (shift, mask, lowest set bit)

XOR of everything is a ^ b ≠ 0. Pick any bit where they differ (the lowest: xor & -xor). That bit splits all numbers into two groups with one single in each, and pairs stay together.

solutions

From brute force to optimal

Add on first sight, remove on second; two values survive.

Toggle each num in a HashSet.
Return the two remaining values.

timeO(n)

One pass of O(1) average operations.

spaceO(n)

The set.

javajava.util.*

1class Solution {2    public int[] singleNumber(int[] nums) {3        Set<Integer> seen = new HashSet<>();4        for (int num : nums) {5            if (!seen.add(num)) seen.remove(num);6        }7        int[] result = new int[2];8        int i = 0;9        for (int v : seen) result[i++] = v;10        return result;11    }12}

Partition by the lowest set bit of a ^ b and XOR each half.

xor = XOR of all nums = a ^ b.
diff = xor & -xor (one bit where a and b differ).
a = XOR of the nums that have that bit; b = xor ^ a.

timeO(n)

Two passes.

spaceO(1)

Three ints.

javajava.util.*

1class Solution {2    public int[] singleNumber(int[] nums) {3        int xor = 0;4        for (int num : nums) xor ^= num;   // = a ^ b, non-zero because a != b5        int diff = xor & -xor;             // lowest bit where a and b differ6        int a = 0;7        for (int num : nums) {8            if ((num & diff) != 0) a ^= num; // only a's group; pairs still cancel9        }10        return new int[] {a, xor ^ a};11    }12}

in the room

How to say it in the interview

talk track

Say why the split is safe: both copies of a duplicated number share every bit, so they always land in the same group.
Mention the edge case xor == Integer.MIN_VALUE. Then -xor == xor and xor & -xor is still the right bit.

traps

Writing (num & diff) == 1. diff is usually not bit 0, so test != 0.

what they ask next

Follow-ups

Why does xor & -xor keep only the lowest 1-bit?

-xor is ~xor + 1: every bit above the lowest 1 is flipped, and the lowest 1 and the zeros below it stay the same. AND-ing the two leaves just that one bit.

Single Number II (LC 137): every other number appears three times?

XOR no longer cancels. Count each of the 32 bit positions across all numbers and keep count % 3 — those bits form the single number. O(32·n) time, O(1) space.

before you submit

Edge cases to test

Only the two singles: [−1, 0].
One single is Integer.MIN_VALUE: −xor overflows back to xor, and xor & −xor still finds the right bit.
The two singles differ only in the sign bit.

practise next