Subj : Re: puzzle
To   : comp.programming
From : cri
Date : Mon Jul 11 2005 08:07 pm

On Sun, 10 Jul 2005 21:41:39 +0000 (UTC), Willem <willem@stack.nl>
wrote:

>Richard wrote:
>) Method 1:  Determine the xor of the numbers 0...n, then xor the
>) sequence.  Xor the two results to get the missing number.
>)
>) Method 2:  Determine the sum of the numbers 0...n, then the sum of the
>) sequence.  The difference of the two sums is the missing number.  To
>) avoid overflow/underflow do the sums module n+1.
>
>I would call those variations on a theme, to be honest.

Fair enough.  Here is another variation on the theme:  If n is odd set
sum = - (n+1)/2.  Loop through the numbers.  Add the odd ones to sum
and subtract the even ones from sum.  Conversely if n is even set
sum = -n/2.  Loop through the numbers.  Add the even ones to sum and
subtract the odd ones from sum.  At the end sum contains the missing
number.
>
>) Method 3: If you can reorder the sequence, partition it into two
>) halves (the criteria can be size, or odd/even), determine which
>) partition is missing an element, and repeat as needed.
>
>Ah, should have thought of that one, especially given the whole
>discussion with the conclusion that it is, in fact, an O(n) solution.

And for a third method we can sort the sequence.  For this data
sorting can be done with O(n) time and O(1) space.  A variation on
this theme that is not quite sorting runs as follows:

Without loss of generality we can use notation that treats the
sequence as being in an array.  Let A be the array, let indexing be 0
based, and let a[i] be the i'th element in A.  As pseudocode:

foreach i in 0...n-1
    select
        A[i] =? i : nil
        A[i] =? n : nil
        else      : begin
            j    = i
            k    = A[i]
            A[i] = n
            repeat
                j    = k
                k    = a[j]
                A[j] = j
                until (k =? n)
            end else
        end select
    end foreach

foreach i in 0...n-1
    if (A[i] =? n) return i
    end foreach
return n

The general idea here is that the data set regarded as a permutation
has one broken cycle.  The regular cycles are simply permuted.  The
broken cycle is permuted in pieces.  In the end A[i] = i except for
the missing item j and there A[j] = n.


            
		

Loop through the array, i = 0...n.  If A[i] = i or A[i] = n do
nothing, else do:
	
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

.