Find coefficients of polynomial that has zeros at certain points

Question

Given a list of values z₀, z₁, ..., z_n-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z₀, z₁, ..., z_n-1 (possibly with repetitions). Try to find a solution or algorithm that can run in time O(nlg²n).

What I've come up with: I know that P(x) has a zero at zj iff P(x) is a multiple of (x - z_j). Therefore, we can check if P(x) mod (x - z_j) = 0 But I'm not sure how to get that runtime or how to proceed further.

Answer 1

What about $p(x)=\prod_{k=0}^{n-1}(X-z_k)$? Use divide-and-conquer and FFT based polynomial multiplication (Schönhage-Strassen) for a fast construction of the product.