Re: puzzle

On Sun, 10 Jul 2005 21:41:39 +0000 (UTC), Willem <willem@xxxxxxxx>
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@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: puzzle
    ... Determine the xor of the numbers 0...n, ... sequence. ... Determine the sum of the numbers 0...n, ... The difference of the two sums is the missing number. ...
    (comp.programming)
  • Re: puzzle
    ... >)> Joe wrote: ... >)>) you have a unordered sequence of the numbers 0 to n with one ... >)>) number missing and the others appearing only once. ... Determine the sum of the numbers 0...n, ...
    (comp.programming)
  • Re: puzzle
    ... Determine the xor of the numbers 0...n, ... )> sequence. ... Determine the sum of the numbers 0...n, ... The difference of the two sums is the missing number. ...
    (comp.programming)
  • Re: puzzle
    ... Determine the sum of the numbers 0...n, ... >sequence. ... The difference of the two sums is the missing number. ... >avoid overflow/underflow do the sums module n+1. ...
    (comp.programming)
  • Re: * says: Definition: sum{i in N} i = 0
    ... "Divergent series" means: ... is the sum of its terms, ... underlying infinite sequence _if_ the limit exists. ... Euler has literally written is not proved true. ...
    (sci.math)