levipearson at gmail.com
Wed Jun 12 03:24:37 MDT 2013
On Jun 11, 2013, at 9:49 PM, Dave Smith <dave at thesmithfam.org> 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
>> 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. :)
More information about the PLUG