Unique Number II
One XOR pass, then split the array on a single differing bit
XOR the whole array and the pairs vanish, but you are left with a XOR b, not a and b. The way out is that a and b are different numbers, so a XOR b is not zero, so at least one bit differs between them. Take the lowest such bit and use it as a sorting rule: numbers with that bit go in one group, numbers without it in the other. Each answer falls in a different group, while every duplicate pair lands together and cancels as usual — so XORing one group gives you a, and a XOR (a XOR b) hands you b for free.
Details
Animated on: nums = [4,6,2,8,2,4] — every number appears twice except two, find both.
Problem:Unique Number IIMedium
One XOR pass, then split the array on a single differing bit
step 1 / 16
nums = [4,6,2,8,2,4] — every value appears twice except two of them. XORing the whole array cancels each pair, but the two survivors land on top of each other in one number, so the real work is splitting them apart.
1FUNCTION twoNonRepeating(nums):2 xorAll <- 03 FOR i <- 0 TO LENGTH(nums) - 1:4 xorAll <- xorAll XOR nums[i]5 mask <- xorAll AND (0 - xorAll)6 a <- 07 FOR i <- 0 TO LENGTH(nums) - 1:8 IF (nums[i] AND mask) != 0:9 a <- a XOR nums[i]10 b <- xorAll XOR a11 RETURN a, b
← / → step · space play · Home restart
Every step in words
Show all 16 steps
- nums = [4,6,2,8,2,4] — every value appears twice except two of them. XORing the whole array cancels each pair, but the two survivors land on top of each other in one number, so the real work is splitting them apart.
- xorAll = 0 XOR 4 = 4 (0100). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 4 XOR 6 = 2 (0010). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 2 XOR 2 = 0 (0000). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 0 XOR 8 = 8 (1000). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 8 XOR 2 = 10 (1010). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 10 XOR 4 = 14 (1110). A value XORed in twice returns to 0, so after this pass only the two lonely numbers are still recorded here.
- xorAll = 14 (1110) is the two answers XORed together, and it is not 0, so they must differ somewhere. Its lowest set bit is bit 1 (mask = 2, 0010): exactly one of the two answers has that bit, which is the wedge that separates them.
- 4 (0100) has bit 1 clear, so it stays out of group A and a is untouched at 0 — the split is what keeps the two answers from cancelling each other.
- 6 (0110) has bit 1 set, so it joins group A and folds in: a = 6. A duplicate always lands in the same group as its twin, so it will still cancel itself here.
- 2 (0010) has bit 1 set, so it joins group A and folds in: a = 4. A duplicate always lands in the same group as its twin, so it will still cancel itself here.
- 8 (1000) has bit 1 clear, so it stays out of group A and a is untouched at 4 — the split is what keeps the two answers from cancelling each other.
- 2 (0010) has bit 1 set, so it joins group A and folds in: a = 6. A duplicate always lands in the same group as its twin, so it will still cancel itself here.
- 4 (0100) has bit 1 clear, so it stays out of group A and a is untouched at 6 — the split is what keeps the two answers from cancelling each other.
- Group A collapsed to a = 6 because every pair inside it cancelled. The other answer needs no second pass: xorAll already holds a XOR b, so b = 14 XOR 6 = 8.
- The two non-repeating numbers are 6 and 8, found in two passes over [4,6,2,8,2,4] with nothing stored but three integers — no hash map of counts was ever needed.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.