🚀 go-pugleaf

In article <4fp1eg$gu3@solutions.solon.com>,
	Christopher R Volpe <volpe@ash.crd.ge.com> writes:
>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?

Given that you cannot use anything larger than an unsigned long to
index the array, that constraint is pretty much nescessary, isn't it?
I took about 30 seconds to find an algorithm that is linear as long as
random access is in a constant time.  If it isn't, then I cannot see
anything smart.  (Ie, if these numbers are on tape, the best way I can
see is to sort them through a merge sort.)

I assume people do not want the actual answers posted here, so just
e-mail me for a solution.  Hint: The average case should detect the
duplicate after inspection of *half* the numbers.
-- 
Eivind Eklund / Job: eivind@funcom.com /  Personal: perhaps@yes.no
FUNCOM don't speak for me, and I return the courtesy.
Message from our sponsor, NSA: ``You are not using DES. Please stop it.''