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