Finding breaks in contiguity

Suppose we have N-K unique numbers in the range 1:N. Let the numbers be a[i], i = 1:N-K. We desire to find the missing numbers, preferably using no more that O(K) extra storage, and, for fixed K, O(N) time. A general method runs as follows:

Compute the quantities, A[k] = sum(i^k), k=1:K. There are standard formulas for these quantities.

Compute the sums b[k] = sum(a[i]^k), k=1:K. Also compute c[k]=A[k]=b[k]. Then the quantities c[k] are symmetric polynomials in the missing numbers. (I disremember whether they are small s or big S.) Transform the quantities c[k] into the coefficients of the polynomial whose roots are the missing elements. Solve the polynomial for its roots.

There are simple (!) methods for doing these computations. The end result is an algorithm that does not alter the numbers, is O(K) in space, and is operations O(K*N+p(K)) for some polynomial in K.

There may be more efficient algorithms. 🙂