Pattern visualizer
Find the Two Non-Repeating Numbers
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. Animated on: nums = [4,6,2,8,2,4] — every number appears twice except two, find both..
One XOR pass, then split the array on a single differing bit
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