Removing even/odd numbers in problem 5.7 of cracking the coding interview
In my opinion, the question is very poorly worded. It says the numbers can only be accessed one bit at a time in constant time. But then allows copying the numbers into two different arrays in O(n) time (each number is copied in constant time) instead of O (n log n) time (where each number needs to have all it's bits copied in O(log n) time).
Step 3 removes non-candidate numbers. If a missing number ith bit is 0, it cannot be any numbers whose ith bit is 1. By removing number whose ith bit is 1, it reduces the candidate number by half.
- ibn Humboldt July 21, 2015Example: Suppose the missing number V is 000. if 0th bit of V is 0, V cannot be any numbers whose 0th bit is 1. Thus 001 and 011 are removed.
- - -
001
010
011