Evaluating a polynomial
There is a polynomial and you have access to a function that evaluates that polynomial at a given number. You don’t know the degree of the polynomial, nor do you know any of the coefficients of its terms. However, you are told that all coefficients are non-negative integers. How many times do you need to call the evaluation function in order to identify the polynomial (that is, to figure out the values of its coefficients)?
We can determine the coefficients of the polynomial by making evaluations of the polynomial at specific values.
First, we can evaluate the polynomial at x = 0. This will give us the constant term of the polynomial.
Next, we can evaluate the polynomial at x = 1. This will give us the sum of all the coefficients.
Then, we can evaluate the polynomial at x = 2. This will give us the sum of the squares of all the coefficients.
We can continue this process and evaluate the polynomial at x = 3, x = 4, and so on, until we have enough equations to solve for all the coefficients.
Specifically, if the degree of the polynomial is n, we can evaluate the polynomial at n + 1 distinct values of x to obtain a system of n + 1 linear equations in n + 1 unknowns (the coefficients of the polynomial). We can then solve this system of equations to determine the values of the coefficients.
Therefore, we need to call the evaluation function at least n + 1 times to identify the polynomial. Note that this is a lower bound, and in practice, we may need to call the evaluation function more than n + 1 times to ensure that we have enough independent equations to solve for all the coefficients.
Your Answer
More puzzles to try-
Black or Brown Gloves
Mr. Brown has 8 black gloves and 8 brown gloves in his closet. He blindly picks up some gloves from ...Read More »Optical Illusion Puzzle – Can you identify what the picture is?
What is shown in the picture? don’t be distracted?Read More »How far can you walk into the woods?
How far can you walk into the woods?Read More »What is it?
What’s often Right when wrong, loudest when quiet and weakest when silent? Hint- If you add a pint of whiskey, ...Read More »eight eights
Can you write down eight eights so that they add up to one thousand?Read More »How many 3’s are in this photo?
Seeds outside
What fruit has its seeds on the outside?Read More »I am in You but not in him riddle
I’m in you, But not in him, I go up, But not down, I’m in the colosseum, But not a ...Read More »Hear me again
You heard me before, yet you hear me again, Then I die, Till you call me again. What am I?Read More »July Equals To…
If March = 43 and May = 39, what does July equals to?Read More »Thief in Grocery store Riddle
A guy walks into a store and steals a $200 bill from the register without the owners knowledge. He then ...Read More »Out of Group
Which of the following words don’t belong in the group and why? CORSET, COSTER, SECTOR, ESCORT, COURTSRead More »Calculate the number of steps
A short man takes three steps to a tall man’s two steps. They both start out on the left foot. ...Read More »Stuck in a House
you are stuck in a house you have four objects to use – Chair, Ladder, Piano, and axe. What would ...Read More »Club membership password puzzle
A man wanted to enter a club, Every member knows the password, 1 man hides himself beside a wall and ...Read More »Dogs and Cats
All of Mrs. John pets are dogs except one, and all her pets are cats except one. How many cats ...Read More »Spotlight puzzle
A conference room contains three separate wall-mounted spotlights – right, left and front of stage. Each is controlled by its ...Read More »Green but no leprechaun Riddle
It is green but not a leprechaun It has lights but It is not a car It has a skirt ...Read More »Bond’s Investigations
On a special event at the prison, 5 prisoners John, Jacob, Krist, Tang, and Dang given a chance to go ...Read More »Runs but never flee
It runs but can never flee. It is often watched, yet never sees. When long it brings boredom, When short ...Read More »