I thought about including the answer that doesn't require branching, but didn't, because it sounded too fucking clever even just proofreading it. The N(N+1)/2 and summation is the answer they probably expect. Gimmicky XOR tricks set you slightly ahead of the pack. Magical bit-twiddling answers and branch elimination make you look pretentious, unless you're literally Carmack.
My point was that solving the problem as posed does not solve the problem inherent in posing the problem. Finding the one missing number in an array of otherwise consecutive numbers means that you were already storing N-1 numbers instead of the one number you wanted. If you stored the missing number instead, it's trivial to construct an array from 1 to N that skips over it. Save space, save time.
And if the profiler says that this problem is on a critical path in an inner loop, optimizing the heck out of it still won't help as much as unmaking the problem entirely, pulling all the cumbersome calculations out into less-used code. If the profiler says that it barely ever gets hit, then there should be zero algorithmic tricks, and the code should be optimized for human readability instead.
As an interview question, it might as well be a cryptic crossword clue, because the solutions that would be put in place by perfectly good developers are not the ones in the back of the textbook.
My point was that solving the problem as posed does not solve the problem inherent in posing the problem. Finding the one missing number in an array of otherwise consecutive numbers means that you were already storing N-1 numbers instead of the one number you wanted. If you stored the missing number instead, it's trivial to construct an array from 1 to N that skips over it. Save space, save time.
And if the profiler says that this problem is on a critical path in an inner loop, optimizing the heck out of it still won't help as much as unmaking the problem entirely, pulling all the cumbersome calculations out into less-used code. If the profiler says that it barely ever gets hit, then there should be zero algorithmic tricks, and the code should be optimized for human readability instead.
As an interview question, it might as well be a cryptic crossword clue, because the solutions that would be put in place by perfectly good developers are not the ones in the back of the textbook.