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.)
--
Robin <[EMAIL PROTECTED]> JabberID: <[EMAIL PROTECTED]>
Hostes alienigeni me abduxerunt. Qui annus est?
PGP Key 0xA99CEB6D = 5957 6D23 8B16 EFAB FEF8 7175 14D3 6485 A99C EB6D
pgpLw9InfaCx0.pgp
Description: PGP signature
