On Jun 11, 2013, at 9:49 PM, Dave Smith <[email protected]> wrote:
> On Jun 11, 2013, at 12:05 PM, Sasha Pachev 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? > > Still thinking about this one. Runtime was not given as a constraint. I > suppose I could simply sort the list and look for holes. Would that violate > the constraints of the challenge? > > I suppose you are fishing for a checksum or lookup table style algorithm. > Still thinking about those approaches. There are a couple of possible number-theoretical solutions for the k-missing generalization, and there is also another solution to the 1-missing problem that does not involve Gauss' sum, but I guess would fall in the checksum category. Yeah, I found a book that covered it on Google. :) /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
