Potential mistake: Chapter 5: bit manipulation "find the missing number" 5.7 per 5th edition

Author: AntymonCreated Nov 27, 2021Updated Feb 3, 2024

Hi,

I have been pondering on the solution to the problem to the above-mentioned question on finding a missing number, and I believe there is a mistake in the solution offered.

Namely, the problem in my opinion is with the deduction rule of a missing bit depending on the counts for a given index. I believe that due to the lack of any constraints on the n, the deduction rule needs to take into account the imbalance caused by the prospect of the list not covering a full resolution of bits positions. E.g., given numbers [0,4] at index 3 we would count four 0s and a single 1. Let's say any of [0,3] numbers is missing. The deduction rule offered would say that due to a count of 0s>1s we should assume 1 is missing for index 3, which is untrue in this case.

At the same time, I have been trying to find the question 5.7 in solutions for 6th edition as per this repo and I failed - perhaps it has been removed between editions 5 and 6 due to the issue described above? In any case I think it would be interesting if someone was able to reconfirm if this mistake conjecture is indeed valid.

Source: careercup/CtCI-6th-Edition