Re: Algorithm to find break in contiguity



On 25 Jan, 17:37, use...@xxxxxxxxxxxxxxx wrote:
I need an efficient algorithm for the following problem:

If you have unique N-1 numbers in the range 1 to N, find the missing
number.

Of course if you could generalize that to finding missing k numbers
from a sample of N-k unique numbers that are in the range 1 to N that
would be better.

Thanks,
Bhta

Obviously, one way to solve this is to have an array and simply note
each number as you read it. Another is to look through the list to see
if there is a 1, then look through again to see if there is a 2, etc.
So, to make this a challenge, I'll assume that you are only allowed to
store a constant amount of information, and that the time you spend
must be limited to some number times N. The technical term for this is
O(N) in time and O(1) in space.

Finding one missing number is easy - just add up the numbers you have
and subtract from what you would have if they were all there.

Two missing numbers can be done too - I think I got this solution from
this very newsgroup a bit ago. Add up all the numbers you have, and
subtract from the total to get a number (call it m) which is the sum of
the two missing numbers. So one missing number is more than m/2 and one
is less than m/2.

Now add up all the numbers in the list that are smaller than m/2,
subtract from what the total would be, and bingo! You have the smaller
missing number. And as you know what the two missing numbers add up to,
you can calculate the larger as well.

I'll leave you to think about whether this can be extended to three
numbers, or indeed generalised further. I don't think you can do in
still in O(N) time, but I may be wrong...

Hope this helps.
Paul.

.

Relevant Pages

  • Re: OT: Math Problem
    ... Subtract a**2 from both sides of the equation, ... the professor frowns, leaves the class for 10 minutes... ...
    (comp.lang.cobol)
  • Re: column count
    ... Maybe I'm missing something, but if you already have the column numbers, why ... can't you just subtract one from the other to get number of columns? ... (email address is on the web site) ... of letters? ...
    (microsoft.public.excel.programming)
  • Re: Subtracting cells
    ... it was the CTRL that I was missing. ... Office book and I could not find it in there I guess it probably is as it is ... > want to subtract E from D in all lines. ...
    (microsoft.public.excel.newusers)
  • Re: Complicated update
    ... Then just add the missing) in: ... since you cannot subtract 10000 from the string Mileage. ... If I explain, this previous total mileage =9500, this travel= 600. ...
    (microsoft.public.access.queries)
  • Re: MISSING NUMBER
    ... Mensanator wrote: ... One number is missing, how to find ... Adding the number then subtract N/2 may not be possible ... Use a math library where "too big to store" isn't an issue. ...
    (comp.programming)