Before you get too excited, this is a probabilistic algorithm, not a deterministic one. Feels weird to call it an "extension" when you lose an absolute guarantee, but still cool nonetheless.
dark-star · 1h ago
It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?
It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer.
The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.
JPLeRouzic · 54m ago
I know XOR only in the context of binary numbers. Is this "XOR trick" more general?
nromiun · 37m ago
Every number on computers is converted to binary internally, so yes this works on decimal numbers too.
The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.