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
.



Relevant Pages

  • Re: find a number
    ... Mark P wrote: ... time, uses constant space, and performs no arithmetic computations on ... the array elements. ...
    (comp.programming)
  • Re: find a number
    ... Mark P: ... time, uses constant space, and performs no arithmetic computations on ... the array elements. ...
    (comp.programming)
  • Re: find a number
    ... On Fri, 24 Mar 2006, Mark P 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. ...
    (comp.programming)