3 ms·
> given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique element For so
by ranger_danger 7mo ago
> given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique element
For some reason this reminds me of the Fourier transform. I wonder if it can be performed with XOR tricks and no complicated arithmetic?
- fluoridation 7mo agoThere's a more general formulation, which is that every value but one must appear even numbers of times, and the one must appear some odd number of times.
- twiceaday 7mo agoHow about every value appears 0 mod n times except one which appears 1 mod n times? :) Solution: xor is just addition mod 2. Write the numbers in base n and do digit-wise addition mod n (ie without carry). Very intuitive way to see the xor trick.