On Tue, Jun 11, 2013 at 12:05 PM, Sasha Pachev <sa...@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. /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */