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
--
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.
