question about missing element in array
- by davit-datuashvili
i have following problem from book introduction algorithm second edition by MIT university
problem is following
An array A[1 . . n] contains all the integers from 0 to n except one. It would be easy
to determine the missing integer in O(n) time by using an auxiliary array B[0 . . n]
to record which numbers appear in A. In this problem, however, 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 j th bit
of A[i],” which takes constant time.
Show that if we use only this operation, we can still determine the missing inte-
ger in O(n) time
please help
