@Lichenga2404: Examine the leftmost bit of each number, using n operations. Make a list of the indices of the numbers with 0 bits and a list of the indices of the numbers with 1 bits. One of the lists will be of even length, and one will be of odd length. The missing number has the leftmost bit that would cause it to be added to the odd length list. Record that bit as the leftmost bit of the answer. Discard the list with the even number of entries. Repeat the above for the second, third, etc bits from the left, using the list of indices produced in the previous iteration. After the rightmost bit is processed, the entire result has been set.
In each case, the list is cut in half, so the algorithm is O(n + n/2 + n/4 + ...) = O(n). This works because the exclusive or of the numbers 0, 1, 2, ..., 2^k - 1 is zero. We can't compute the exclusive or directly because that would be O(n log n), so we compute it one bit at a time, operating only on the numbers that have the same leading bits as the missing number. Dave On Nov 3, 2:50 am, lichenga2404 <lichenga2...@gmail.com> wrote: > You are given an array A of n distinct integers , expressed in binary. > Each integer is in the range [0,n] .As there are n+1 values in this > range, there is exactly one number missing .As a single operation, you > may access the jth integer(A[i][j]) . Note that it would take O(nlogn) > time to read the full array. > > Give an O(n) algorithm to determine which integer is missing , and > justify its correctness, You may assume that n = 2^k - 1 for some > integer k. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
