In this task you'll be given a set of N points (x1,y1),…,(xN,yN) with distinct xi values and your task is to interpolate a polynomial through these points. If you know what Lagrange interpolation is you can skip this section.
The goal of a polynomial interpolation is to construct the (unique) polynomial p(x) with degree N-1 (for higher degrees there are infinite solutions) for which p(xi) = yi for all i = 1…N. One way to do so is to construct N Lagrange basis polynomials and form a linear combination. Such a basis polynomial is defined as follows:
As you can see if you evaluate li at the points x1,…,xi-1 ,xi+1,… ,xN it is 0 by construction and 1 for xi, multiplying by yi will only change the value at xi and set it to yi. Now having N such polynomials that are 0 in every point except one we can simply add them up and get the desired result. So the final solution would be:
- the input will consist of N data points in any reasonable format (list of tuples, Points, a set etc.)
- the coordinates will all be of integer value
- the output will be a polynomial in any reasonable format: list of coefficients, Polynomial object etc.
- the output has to be exact - meaning that some solutions will have rational coefficients
- formatting doesn't matter (
1 % 2for
1/2etc.) as long as it's reasonable
- you won't have to handle invalid inputs (for example empty inputs or input where x coordinates are repeated)
These examples list the coefficients in decreasing order (for example
[1,0,0] corresponds to the polynomial x2):
[(0,42)] ->  [(0,3),(-18,9),(0,17)] -> undefined (you don't have to handle such cases) [(-1,1),(0,0),(1,1)] -> [1,0,0] [(101,-42),(0,12),(-84,3),(1,12)] -> [-4911/222351500, -10116/3269875, 692799/222351500, 12]