Skip to main content
5 of 14
added an explanation
Arnauld
  • 197.8k
  • 20
  • 179
  • 650

#JavaScript (ES7),  193 181 160  159 bytes

Returns \$(a_0,a_1,...,a_k)\$ with some possible trailing zeros.

v=>v.map((_,i)=>(D=m=>+m||m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0))((g=i=>v.map((n,y)=>v.map((_,x)=>x==i?n:y**x)))(i))/D(g()))

Try it online!

(the above test link filters out floating point approximation errors by rounding the results; this is actually only needed for the penultimate test case)

###How?

We use Cramer's rule to solve a system of linear equations based on a square Vandermonde matrix.

The Vandermonde matrix of size \$n\times n\$ that we are using is defined as:

$$Vn=\begin{pmatrix} 1&0&0&...&0\\ 1&1&1&...&1\\ 1&2&4&...&2^{n-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&n-1&(n-1)^2&...&(n-1)^{n-1} \end{pmatrix}$$

The coefficient \$a_i\$ of the polynomial is computed by computing the determinant of the matrix obtained by replacing the \$i\$-th column of \$V_n\$ with the input vector, and dividing by the determinant of \$V_n\$.

###Example for \$(4,2,12,52,140)\$

The constant coefficient \$a_0\$ is given by:

$$a_0=\begin{vmatrix} 4&0&0&0&0\\ 2&1&1&1&1\\ 12&2&4&8&16\\ 52&3&9&27&81\\ 140&4&16&64&256 \end{vmatrix}/|V_5|=\frac{1152}{288}=4$$

Arnauld
  • 197.8k
  • 20
  • 179
  • 650