3 ms·
It took me a minute to figure out the last step of the final example since the author doesn’t quite spell it out. So for anyone else who’s feeling a little slow
by lemoncucumber 4y ago
It took me a minute to figure out the last step of the final example since the author doesn’t quite spell it out. So for anyone else who’s feeling a little slow:
Once you’ve partitioned the search space into “values where the ith bit is 0” and “values where the ith bit is 1” (for example, even and odd values if it happens to be the least significant bit), then you can simply iterate through all the input values and xor together all the values where the ith bit is 0, then xor those with all possible values where the ith bit is 0, and you’ve found one of the missing values. Repeat the process with 1 instead of 0 to find the other.