[Update: This is why you dont write down things in the middle of the night… the sum I wrote up and *did not notice* is totally wrong. I also made an error on another problem I wrote down. Anyway, the error here is that the sum from 1 to N-1 does match with [((N-1)+1) + ((N-2)+2) + …] becomming N^2/2 not N/2. I just forgot to write down N^2, got distracted, then came back and finished it off that way. Crazy. Yet again I need to never do math after midnight. Anyway ignore what I wrote up below – essentially you have the same solution but the sum you compare with is N^2/2 for a list from 1…N-1 in value. Not going to delete the post as this makes a good example of a simple mistake that can even seem resonable if you dont doubble check your finial result! So might stick this in the book as an example of what NOT to do. ;-) ]
So when preparing for my Amazon interview I brushed back up on computer science as opposed to nocking the rust off my coding skills (read getting back to where I could code my way out of a paper bag). Anyway one of the things I ran across when prepping for the interview was a numeric sum problem. Basically you are given a list of numbers ranging in value from 1 to N, in unsorted order. One of the numbers is either missing or duplicated – write a number to find the function.
One solution is to sort the list and then search it for the missing / repeated value. Should be able to do this in O(nlogn) time. I need to check but I *think* a radix sort would work here for N time. A much better solution is to remember the series equivalent of 1…N. Then you can sum the numbers you were given, compare that number with the series equivalent, and just know the answer. Since it takes only one pass over the list it works in O(N) time too.