The Brief

A polynomial is a function where a variable is raised to various positive integer powers of x, each with a constant coefficient, and summed together. For example, f(x) = 2x^3 + 4x^2 + 6.

The aim of this kata is to find the lowest degree polynomial that exactly fits the kata input, a sequence of integers. These integers will always be the first n values of f(x) for x = 1, 2, 3, ...n. The degree of a polynomial is simply the largest power of x in the polynomial, which would be 3 in the above example.

An Example:

• With the input [3, 9, 19, 33], we immediately see that no linear polynomial (such as f(x) = 2x + 3) will work, as the difference between consecutive terms is not constant.
• A quadratic polynomial with an x squared term does work though, as the second difference is constant:

  . 3,  9,  19, 33
  .   6,  10, 14
  .     4,   4
  

• With a bit of maths we can work out the resulting quadratic as f(x) = 2x^2 + 1, so we would return [2, 0, 1], where each element of the array corresponds to the coefficients of the decreasing powers of x (notice the included 0 to indicate an x^1 coefficient of 0.)

Your task is to generalise this to any degree of polynomial, for any input. The input will always be a sequence of integers, as will be the coefficients of the expected polynomial. Since there are infinite polynomials that fit any given sequence of numbers, you must return the single lowest degree polynomial that fits.

The Tests

Your code should be fairly efficient, as you will be tested on:

• 100 polynomials of degree <= 5 (largest term is x^5) with up to 200 input values,
• 100 polynomials of degree <= 25 with up to 200 input values,
• 25 polynomials of degree <= 100 with up to 150 input values.

Good luck!