-1

Given an array of n unique integers in [1, n], take random k elements away from the array, then shuffle it to be left with an array of size n-k of integers of size n-k

I want to find those k integers in the best complexity.

If k==1, we can sum all the elements in the array, and the missing element would be the difference between n(n+1)/2 (sum of all numbers from 1 to n) and the sum of the array elements.

I would like to extend this algorithm to k missing elements by k equations, but don't know how to build the equations. Can it be done?

Gulzar
  • 23,452
  • 27
  • 113
  • 201
  • 3
    [Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing](https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe) – user3386109 Jun 09 '21 at 22:28

2 Answers2

0

Lets assume a[1], a[2], a[3], ....a[n] are the original unique integers and b[1], b[2],...b[n-k] are the integers after k integers are removed.

Sort the arrays a and b.

For each adjacent pair (i,i+1) in b do a binary search for b[i], b[i+1] in array 'a' and get the indices lets say p, q

If q != p + 1 then all the integers in array a between p, q are among the k integers taken away.

The complexity should be O(n log n )

SomeDude
  • 13,876
  • 5
  • 21
  • 44
  • I should clarify that this is not considered efficient, just as the original `k=1` algorithm could be solved by sorting but summation gives `o(n)`. Also this does not answer the question. – Gulzar Jun 09 '21 at 22:37
  • 1
    If you are only after the equations then the link shared in the comments should be your answer. – SomeDude Jun 09 '21 at 22:43
  • @Gulzar Computing `sum(i: [1..N]) i**k for all k: [1..K])` takes `O(N * K**2)` multiplications. So then the question is, which is larger `logN` or `K**2`. And that ignores the time needed to solve `K` equations in `K` variables. It also ignores the fact that you'll need to use a bignum library to compute the sums. So sorting in the input, and looking for gaps is the only sensible answer. – user3386109 Jun 09 '21 at 22:45
-1

Yes it can. It is not pretty though.

You need to realize that in a [1, n] range

  • the sum of squares is n(n + 1)(2n + 1) / 6
  • the sum of cubes is n**2(n + 1)**2 / 4
  • etc

The devil is in etc. The general formula of summing kth powers is

Sum(i: [1..n]) i**k = 1/(k+1) Sum(j: [1..k]) (-1)**j binom(k+1, j) Bj n**(k-j+1)

where Bj are the Bernoulli's numbers. It is a polynomial of the k+1th degree.

The Bernoulli numbers are notoriously hard to compute, and the resulting system of equations is not too pleasant to deal with.

Assuming that you overcame all the computational problems, the complexity will be O(nk).

user58697
  • 7,808
  • 1
  • 14
  • 28