Rashair
commented
9 months ago Was it the same as 17.4 in the 6th edition?
Missing Number: An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jt h bit of A[ i]," which takes constant time. Write code to find the missing integer. Can you do it in 0( n) time?
I had the same thought, but it actually works.
The explanation for MSB is invalid though - the number of bits at MSB won't be the same if the N is different than 2^k - 1
It works at MSB, because at this point we basically have 2 options to choose from.
We have established a pattern: X010101010...01101 and here MSB can be 0 or 1.
There're only 2 numbers with this pattern.
If one with 0 is missing, then (count of 0s) < (count of 1s = 1)
If one with 1 is missing, then (count of 0s = 1) > (count of 1s = 0)
It seems that it accidentally worked :D
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.