Plug topics

John Shaver bobjohnbob at gmail.com
Tue Jun 11 21:19:47 MDT 2013


On Tue, Jun 11, 2013 at 12:05 PM, Sasha Pachev <sasha at asksasha.com> wrote:

> >Remember when PLUG actually discussed Linux issues, before turning

Part 1 - easy, you frequently see this in job interviews. Maybe not anymore
> because everybody knows it. You have a list of N unordered elements that
> contains unique numbers from 1 to N+1 with one missing. Using the amount of
> RAM that will be the same regardless of N can you find the missing number
> in one pass? Hint if you need one - remember how Gauss annoyed his math
> teacher.


I've never seen this problem before, but I would say, sum up all the
numbers in the list in one pass and subtract from ((n + 1)^2 + n + 1)/2.



def find_missing(list):
    N = len(list)
    total = (pow(N + 1, 2) + N + 1 )/2
    sum = 0
    for ele in list:
        sum = sum + ele
    print(total - sum)



> Part 2 - harder - can you do this if two numbers are missing?  Is your
> solution robust enough to avoid register overflow? Can you do it without
> resorting to BigInt arithmetic?


I can't find a way to do this in one in a single pass that is O(1) for
memory usage.  At least not one that doesn't overflow if N > 12 or so.

I'd like to see the answer if there is one.


More information about the PLUG mailing list