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
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.
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