Last Updated: 4 Dec, 2021
Polynomials
Ninja
Asked in company
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].
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
Approaches
Multiply every coefficient in B with every coefficient in A and add to the final result. Return the final result.
Algorithm:-
- Initialize an array named ANS of length 2*N.
- Iterate through 0 to N.(Letās say the iterator is i).
- Iterate through 0 to N.(Letās say the iterator is j).
- Add A[i] * B[j] to ANS[i+j].
- Iterate through 0 to N.(Letās say the iterator is j).
- Return ANS.
Use Fast-Fourier Transformation to multiply the polynomials faster. So let there be a polynomial A(x) with degree nā1, where n is a power of 2, and n>1.
We divide it into two smaller polynomials, the one containing only the coefficients of the even positions, and the one containing the coefficients of the odd positions:
Read more about FFT Transformation here:- https://cp-algorithms.com/algebra/fft.html
Algorithm:-
- Initialize a variable named K with 1.
- Start a while loop to make K a power of 2 such that K is greater than 2*N.
- Resize arrays A and B with size K with names FA and FB respectively.
- Apply FFT transformation on A and B.
- Iterate from 0 to N.(Letās say the iterator is i).
- Multiply FA[i] with FB[i].
- Apply FFT Transformation on A.
- Initialize an array named ANS of length 2 * N - 1.
- Iterate from 0 to N.(Letās say the iterator is i).
- Update ANS[i] as the real value of FA[i].
- Return ANS.