Re: find a number
 From: Logan Shaw <lshawusenet@xxxxxxxxxxxxx>
 Date: Sat, 25 Mar 2006 19:45:24 GMT
Steve O'HaraSmith 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'HaraSmith
 find a number
 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):
Relevant Pages
