Re: find a number
- From: Logan Shaw <lshaw-usenet@xxxxxxxxxxxxx>
- Date: Sat, 25 Mar 2006 19:45:24 GMT
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.
v = a;
if (a[v] == v)
a = 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 multiple times, it conflicts with