Interview Question for Senior Software Engineer at Goldman Sachs:

hint sum (n) = n X (n+1)/2

One problem with that solution (sum) is that if the sum of numbers is of exorbitant size, you run a risk of overflow, given that there's no limit imposed on N.

You can sort the array, but if you don't want modify the user's array, you'll need to make a copy...which depending on the size of the array, might be expensive.

An alternative that I thought of would be to create a bitmap for each element (initializing all bits to 1). Then pass through the vector once and set the corresponding bit 0. After one pass through, you can make a second pass to determine which "sectors" still contain set bits and can extrapolate the missing value accordingly.

Worst case O(2N)

A strategy might be to impose one of the two methods, depending on the size of the array, but sorting inevitably has a floor of O(N), unless you're going to take a probabilistic guess and skip over elements you think might already be sorted. Most algorithms are O(n log n) because the need to visit every element, and the revisiting of some elements to perform the proper placement.

This post has been removed. Please see our Community Guidelines or Terms of Service for more information.