Hi , Dave Why to do like this :"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." ?
2010/11/3 Dave <dave_and_da...@juno.com> > @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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- licheng -- 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.
