Re: find a number

Steve O'Hara-Smith wrote:
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;

If we are solving a new problem, then possibly. But if we are solving
the problem posted by the person who started this thread, then this is
not a solution, because the original problem states this restriction:

Assume that I can access each element of the array only once.

Since that algorithm accesses a[0] multiple times, it conflicts with
that restriction.

- Logan