Polynomials

Ninja
0/200
Average time to solve is 60m
profile
Contributed by
24 upvotes
Asked in company
Codenation

Problem statement

You are given two polynomials. You have to multiply them and print the result.

You are given the coefficients of the first and second polynomials denoted by array A and array B respectively. You have to return the coefficient of the resulting polynomials.

Example:- 
A = [1,2,3]
B = [3,2,1]

ANSWER:- The answer should be [3,8,14,8,3] as the polynomials are x^2 + 2x + 3 and 3x^2 + 2x + 1.On multiplying we get 3x^4 + 8x^3 + 14x^2 + 8x + 3 and hence the answer is [3, 8, 14, 8, 3].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains an integer ‘N’ denoting the maximum degree of polynomial A and polynomial B.

The next line of every test case contains an array ‘A’ denoting the coefficients of the first polynomial.

The next line of every test case contains an array ‘B” denoting the coefficients of the second polynomial.
Output Format : 
For each test case, return an array denoting the coefficients of the resulting polynomial.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^4
1 <= A[i] <= 500
1 <= B[i] <= 500

Time Limit = 1 sec

Sample Input 1 :
2
3
1 0 1
2 1 0
1
1
1
Sample Output 1 :
2 1 2 1 0
1
Explanation for Sample Output 1 :
In the first test case, the polynomials are x^2 + 1 and 2x^2 + x. On multiplying we get 2x^4 + x^3 + 2x^2 + x and hence the answer is [2, 1, 2, 1, 0].
In the second test case, the polynomials are 1 and 1. On multiplying we get 1 and hence the answer is [1].
Sample Input 2 :
1
2
1 1
1 1
Sample Output 2 :
1 2 1
Hint

Multiply every element A with every element in B.

Approaches (2)
Brute Force

Multiply every coefficient in B with every coefficient in A and add to the final result. Return the final result.

 

Algorithm:-

 

  1. Initialize an array named ANS of length 2*N.
  2. Iterate through 0 to N.(Let’s say the iterator is i).
    1. Iterate through 0 to N.(Let’s say the iterator is j).
      1. Add A[i] * B[j] to ANS[i+j].
  3. Return ANS.
Time Complexity

O(N ^ 2), where N is the highest degree of polynomial A and polynomial B.

We are iterating every coefficient in A with every coefficient in B, so the time complexity is O(N ^ 2).

Space Complexity

O(N), where N is the highest degree of polynomial A and polynomial B.

We are using an array of size 2 * ‘N’ to store the coefficients of the resulting polynomial, so the time complexity is O(N).

Code Solution
(100% EXP penalty)
Polynomials
Full screen
Console