Re: searching for missing element in an array

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

Neat idea, although you would have to consider cases of even and
odd n (for n=3, n(n-1)/2 != 1 (mod 4)); I would also use modulo n,
but this is just a personal preference (you still get two cases).

--
Alex
.

Relevant Pages