🚀 go-pugleaf

In article <4fu8m9$9oh@solutions.solon.com>,
Gene Gorokhovsky  <geneg@kandasoft.com> wrote:
>Christopher R Volpe wrote:
>: 
>: James Hu wrote:
>: > >>>>> In article <4fa794$2lb@solutions.solon.com>,
>: > >>>>> "Gene" == Gene Gorokhovsky <geneg@kandasoft.com> writes:
>: >
>: > [ Find the number that appears twice in a list of N numbers which
>: >   contain all numbers from 1..N-1 in linear time, using constant
>: >   addtional space. ]
>: 
>: Any bounds on N here? Is this a general algorithms question where N can
>: grow arbitrarily large? Or are we relying upon C-specifig things, like
>: fitting everything in an unsigned long?
>
>The original problem was formulated with N=100. I would not give
>any points off for assuming N is unsigned short.


The only assumption you need is an unsigned integral type that can hold N.
You need an unsigned type because the standard solution (summing all the
numbers in the table and checking against sum_{i=1}^{n-1} i) might overflow,
and this will get you in trouble with signed arithmetic.

As unsigned arithmetic has to behave `as if' it were modular arithmetic,
you may ignore overflow and get the correct answer nevertheless :-)

[ can't get back to Chris Volpe through email, but his original message
triggered this reflexion]

BTW, the `solution' of using the list elements' sign to count the
number of times a given element appears is wrong: you are using additional
storage, namely n additional bits.

-- 
[nosave]<http://www.eleves.ens.fr:8080/home/espie/index.html>
microsoft network is EXPLICITLY forbidden to redistribute this message.
`Moon purismu powa, make up.... Tsuki ni kawatte, oshiokiyo !'
	Marc Espie (Marc.Espie@ens.fr)