Re: find a number



On Fri, 24 Mar 2006 19:12:35 GMT
Mark P <usenet@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

There's also a cute algorithm for this problem which runs in linear
time, uses constant space, and performs no arithmetic computations on
the array elements.

I think this works.

while (1)
{
v = a[0];
if (a[v] == v)
return v;
a[0] = a[v]
a[v] = v;
}

--
C:>WIN | Directable Mirror Arrays
The computer obeys and wins. | A better way to focus the sun
You lose and Bill collects. | licences available see
| http://www.sohara.org/
.