Re: searching for missing element in an array

On Fri, 30 May 2008 04:25:42 +0000, Richard Heathfield
<rjh@xxxxxxxxxxxxxxx> wrote:

[snip]

"The trick" is therefore guaranteed to work provided only that n(n-1)/2
does not exceed the maximum possible value for a number on the host
system.

That should be n(n+1)/2. As for my suggestion else where, the
computations should be done modulo n+2, and the requirement is
that the maximum possible value for a number be greater than
2*n+1.

Better yet, in C use unsigned arithmetic. Overflow will not
matter since the arithmetic is automatically done in modulo
arithmetic. Willem was right after all.



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