@Cheng: There are n numbers in the array, and each of them is k bits
long, where k = log_2(n+1). Thus, to read all k bits of all n numbers
takes n*k operations, which is O(n log n).
Dave
On Nov 7, 1:36 pm, cheng lee <lichenga2...@gmail.com> wrote:
> Thank you for your detailed explaination.
>
> But I also have some question: why does the problem tell us to note that
> it would take O(nlogn) time to read the full array ? How can we calculate
> that reading the full array ( in binary form) is O(nlogn) ?
>
> 2010/11/6 Dave <dave_and_da...@juno.com>
>
>
>
>
>
> > @Cheng: This is the "divide" of divide and conquer. In more detail,
> > the numbers from 0 to 2^k - 1 have 2^(k-1) zeros and 2^(k-1) ones in
> > each bit position. E.g., let k = 3. Then the numbers are
> > 0=000
> > 1=001
> > 2=010
> > 3=011
> > 4=100
> > 5=101
> > 6=110
> > 7=111
> > Notice that there are 4 zeros and 4 ones in each bit position. If we
> > have 2^k - 1 distinct numbers from 0 to 2^k - 1, then there one of the
> > numbers from 0 to 2^k - 1 is missing. That number will have either a
> > zero or a one in the leftmost bit position. So when you make a list of
> > the numbers with a zero bit in the leftmost position and another list
> > of the numbers with a one bit in the leftmost position, one of those
> > lists will have 2^(k-1) numbers and the other list will have 2^(k-1) -
> > 1 numbers. The shorter list would be filled out to length 2^(k-1) if
> > the missing number were not missing.
>
> > Let's take a look at the entire algorithm. Suppose k = 3 and the
> > number 5 is missing, with the rest of the numbers in "random" order:
> > a[0]=010
> > a[1]=111
> > a[2]=001
> > a[3]=000
> > a[4]=110
> > a[5]=011
> > a[6]=100
> > Then the list of indices of the numbers with a zero leftmost bit is
> > {0,2,3,5}, and the list of indices of the umbers with a one leftmost
> > bit is {1,4,6}. The list of indices of the numbers with the leftmost
> > one bit is the shorter list, so record that the leftmost bit of the
> > missing number is 1, and discard the longer list.
>
> > Now analyze the second bit of the numbers whose indices are in the
> > remaining list: The list of indices of the numbers with a zero bit in
> > the second position is {6}, and the list of indices of the numbers
> > with a one bit in the second position is {1,4}. The first list is the
> > shorter one, so note that the second bit of the missing number is 0,
> > and discard the longer list.
>
> > Now analyze the rightmost bit of the numbers whose indices are in the
> > remaining list: The list of indices of the numbers with a zero bit in
> > the rightmost position is {6}, and the list of indices of the numbers
> > with a one bit in the rightmost position is {}, i.e., empty. The
> > second list is the shorter one, so note that the third bit of the
> > missing number is 1.
>
> > Now you have all three bits of the missing number 101, so the missing
> > number is 5.
>
> > The work is the number of inspections of bits in the input numbers,
> > which is 7 + 3 + 1 = 11. This is less that 2n. In general, for any
> > number of bits, the work will be less than 2^k + 2^(k-1) + 2^(k-2)
> > + ... + 2^1 + 2^0 - 2(2^k) - 1 < 2n, so the work is O(n).
>
> > Dave
>
> > On Nov 6, 6:18 pm, cheng lee <lichenga2...@gmail.com> wrote:
> > > 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>
> > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > .
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > licheng- Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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- Hide quoted text -
>
> - Show quoted text -
--
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.
