Here is the solution in PERL (this takes an Integer arg for the size
of the list of numbers, and outputs the list, the walks through the
lists, and the single repeating element) :
#!/usr/bin/perl
# setup problem -- this will embed the numbers 1...(N-1) into cells
1...N with one duplicate
# first, set array[x] = x
for(my $i=1;$i<=$ARGV[0];$i++) {$array[$i] = $i;}
# next, pick one of the entries on 1...(N-1) to replace entry N
$array[$ARGV[0]] = $array[int(rand(($ARGV[0]-1)))+1];
# now shuffle them. And the setup is complete.
for($i = 0; $i<$ARGV[0]*100; $i++) {
$rand1 = int(rand($ARGV[0]))+1; $rand2 = int(rand($ARGV[0]))+1;
$swap = $array[$rand1]; $array[$rand1] = $array[$rand2];
$array[$rand2] = $swap;
}
# Output list...
for($i=1;$i<=$ARGV[0];$i++) {print $i . "\t" . $array[$i] . "\n";}
print "-------------\n";
# Output list... show closures of walks
for($i=1;$i<=$ARGV[0];$i++) {
print $i;
local(%seen);
local($walker);
$walker=$i;
while(!exists $seen{$array[$walker]}){
print " -> " . $array[$walker];
$seen{$walker} = "blahblah";
$walker = $array[$walker];
}
print " -> " . $array[$walker];
print "\n";
}
print "-------------\n";
# here is the actual solution!!
local($tortoise);
local($haire);
$tortoise = $haire = $ARGV[0];
for(;;) {
$tortoise = $array[$tortoise];
$haire = $array[$array[$haire]];
if ($array[$tortoise] == $array[$haire]) { last; }
}
local($fromStart);
$fromStart = $ARGV[0];
while($array[$fromStart] != $array[$tortoise]) {
$fromStart = $array[$fromStart];
$tortoise = $array[$tortoise];
}
$tortoise = $array[$tortoise];
print "The repeating element is: $tortoise\n";
There are only 3 pointers needed. Thus this is O(1) storage. It is
also clearly linear in time complexity.
On Aug 16, 1:41 pm, dsha <[EMAIL PROTECTED]> wrote:
> Hi there,
>
> I'm interested in the following problem: there is an array of integers
> that contains each element only once except for one element that
> occurs exactly twice. Is there a way to find this element faster than
> O(n*log n) and with constant extra memory? If no, how can I prove it?
>
> Thanks in advance for ideas.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
