Mysterious Polynomial

You are given a polynomial P(x) of unknown degree with coefficients which are non-negative integers. You don’t know any of the coefficients, but you are allowed to evaluate the polynomial at any point you choose. What is the smallest number of evaluations you need to use, so that can find the degree and the coefficients of P(x)?

SOLUTION

Just 2 evaluations are enough. First, get P(1). This will give you an upper bound on the number of digits of the largest coefficient of the polynomial, let’s say that is N. Now evaluate the polynomial at the point M = 10 to the power of N. This will make all of the coefficients of P appear in the number P(M), separated by strings of zeros.