Robin wrote:
On Tuesday 11 October 2005 00:54, Suvajit Sengupta wrote:
If the array A is a list of consecutive N natural numbers,
then missing number,n = Sum of N natural numbers + Sum of the numbers
in Array A.
That's a nice solution. It can be enhanced slightly with the use of that
thing that someone famous came up with (was it Gauss?):
Assumptions:
1) the set of numbers would be consecutive if it were sorted, with the
exception of the missing number.
2) the list starts at 1 (although the 1 can be missing, that's OK)
Work out the sum of the numbers in the list, assuming it was complete:
$sum = ($list[-1] + 1)*((@list + 1) / 2)
Work out the real sum of the values in the list:
foreach (@list) { $realSum += $_; }
Find the missing number:
$missing = $sum - $realSum;
Because I should be doing something else but can't be bothered, I'll break
down the first part and explain it. It's really quite neat.
Imagine a complete list of numbers: 1+2+3+4+5+6+7=28
This can also be represented as: (1+7)+(2+6)+(3+5)+(4)=28
Note also that 1+7=8, 2+6=8 and so on, the exception being the 4, but
we'll deal with that soon.
Now, we have as many of those pairs as we have (numbers in the list)/2
If you happen to have an odd-numbered list (such as above), you end up
having an x.5 result. That takes care of the 4 (given 8*0.5=4).
So you take the value from the pairs, in this case 8, multiply it by the
number of pairs, in this case 3.5 ... and you have the sum of the numbers
in the list.
Clearly, the difference between this value and the actual sum must be the
missing number. So you can get your solution in O(n) time rather than
O(n^2).
Cool huh? :)
(BTW: my "not knowing the above" solution would have been to sort the
list, then search for the missing one.)
True but if you already have a sorted list with only one missing value
you can get to the result even faster. Even in O(lg(n)) time (log_2 (n))
that is. E.g:
use POSIX;
use strict;
# Array is an array going from 0 to $end with one value missing
my @array = qw/0 1 2 3 4 5 7 8 9 10 11 12 13/;
my $begin = 0;
my $end = 13;
while($begin != $end){
my $n = floor(($begin+$end)/2);
if($array[$n] != $n){
# Go to the left
# If else logic is needed to reach the stop condition
if($end==$n){
$end--;
}else{
$end=$n;
}
}else{
# Go to the right
if($begin==$n){
$begin++;
}else{
$begin=$n;
}
}
}
print $begin . " is missing\n";
(I agree on the btw)
gr
E
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>
