Plug topics

Joshua Marsh joshua at themarshians.com
Tue Jun 11 18:25:27 MDT 2013


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

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

Is the goal of part two to accomplish all of the questions at the same
time? I can think of an easy way to find two missing, or even x missing,
but not without some form of summation which, given a sufficiently large N,
would to overflow. If the last part is solvable in one algorithm, I'd
definitely like to see a solution.


More information about the PLUG mailing list