Open
Description
For any values of k or n greater than 2 the fastest algorithm is probably to simply use a hash-table which would be amortized O(n). But the answer given suggests doing a O(n^k) grid search which (in my opinion) isn't a good idea.
Another "pure" mathematical approach would be to let the non-missing values be p_1,...,p_{n-k} which are the roots of the polynomial f(x)=(x-p_1)...(x-p_{n-k})=x^{n-k}+s_1x^{n-k-1}+...+s_{n-k-1}x+s_{n-k} and calculate the symmetric homogeneous polynomials s_1,...,s_{n-k} via Newton's identities. Then we plug 1,2,...n into the polynomial f and the missing values are the non-roots. Depending on the value of k this could be faster than the grid search (but still a lot slower than the hash table).
Metadata
Metadata
Assignees
Labels
No labels