Re: searching for missing element in an array

On Fri, 30 May 2008 05:21:46 +0000 (UTC), Willem
<willem@xxxxxxxx> wrote:

Richard wrote:
) "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.

Or if your host system can do modulo-X (*) math properly.
Note that you will have to be quite precise in how you calculate n(n-1)/2.

*) X being, for example, 2^32

Better yet, do the arithmetic module n+1. Note that n(n-1)/2 = 1
modulo n+1. If k is the missing number and S is the sum of the
n-1 numbers modulo n+1, then k = n+2-S.


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