Evaluate the Polynomial

Easy

0/40

Average time to solve is 20m

Contributed by

5 upvotes

Asked in companies

Problem statement

You are given two arrays of coefficients and degrees of a polynomial expression. You need to simplify the polynomial in general form by evaluating and simplifying the expression.

For Example:

If the given polynomial equation is “5x ^ 3 + 2x ^ 3 + 6x ^ 4 + 2”. There are two terms of exponent or degree 3 and they are 5x ^ 3 and 2x ^ 3. Both these terms will get added and form 7x ^ 3, so the given polynomial will be simplified as 7x ^ 3 + 6x ^ 4 + 2. Now by arranging the expression in the decreasing order of the degrees, we will have 6x ^ 4 + 7x ^ 3 + 2 and hence the result.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases/queries to be run. 
Then the test cases follow.

The first line of each test case contains a positive integer 'N' which represents the number of terms in the polynomial.

The second line of each test case contains 'N' integers denoting the coefficients of the polynomial.

The third line of each test case contains 'N' integers denoting the degree of the polynomial.

Output Format :

For each test case, print a single line containing two space-separated integers denoting the coefficient and degree of the term respectively.
The result will be printed in descending order of the degrees.

The output for each test case will be printed in a new line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

0 <= T <= 10
1 <= N <= 10 ^ 5
-10 ^ 5 <= coefficient <= 10 ^ 5
0 <= degree <= 10 ^ 5

Time Limit: 1 sec.

Sample Input 1 :

Sample Output 1:

4 7
3 2
2 1

Explanation of Input 1 :

For the first test case, we have no non-zero term so return an empty array.

For the second test case, if we represent our input to the polynomial expression it will be “2x ^ 2 + 1x ^ 2 + 4x ^ 7 + 2x“ so after simplifying it will be “4x ^ 7 + 3x ^ 2 + 2x” thus output would be 
4 7
3 2
2 1

Sample Input 2 :

1
5
-1 2 3 6 -1
4 3 1 4 0

Sample Output 2:

Explanation of Input 2 :

Representing the input to the polynomial expression it will be “-1x ^ 4 + 2x ^ 3 + 3x ^ 1 + 6x ^ 4 + -1“ so after simplifying and arranging it in descreasing order of the exponent it will be “5x ^ 4 + 2x ^ 3 + 3x -1” thus output would be 
5 4
2 3
3 1
-1 0

Hint 1

Try to use a map that will store the coefficients of the given exponents.

Approaches (1)

Approach 1

Using a map to store coefficients

Initialise a map which will store the coefficients as value and exponent as key.
For every term in the polynomial, update the coefficients in the map.
If the coefficient becomes zero then remove the entry from the map.
Sort the key values in descending order.
Initialize the answer array.
Add all non-zero coefficients in the array and return it.

Time Complexity

O(N * logN), where ‘N’ is the number of terms in the polynomial and ‘K’ is the max exponent of the polynomial.

We are sorting the array and traversing through it once. Thus, the overall complexity becomes O(N * logN).

Space Complexity

O(K), where ‘K’ is the max exponent of the polynomial.

We need an array of length at most ‘K’ to store the result.

(100% EXP penalty)

Evaluate the Polynomial

Console