# 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.

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

.

**References**:**find a number***From:*murali@pune

**Re: find a number***From:*Sc0rpi0

**Re: find a number***From:*Mark P

**Re: find a number***From:*Steve O'Hara-Smith

- Prev by Date:
**Re: Checking for Modification to a Set of Files** - Next by Date:
**Re: Checking for Modification to a Set of Files** - Previous by thread:
**Re: find a number** - Next by thread:
**Re: find a number** - Index(es):