You are given two integer arrays poly1 and poly2, where the element at index i in each array represents the coefficient of xi in a polynomial.
Let A(x) and B(x) be the polynomials represented by poly1 and poly2, respectively.
Return an integer array result of length (poly1.length + poly2.length - 1) representing the coefficients of the product polynomial R(x) = A(x) * B(x), where result[i] denotes the coefficient of xi in R(x).
Example 1:
Input: poly1 = [3,2,5], poly2 = [1,4]
Output: [3,14,13,20]
Explanation:
A(x) = 3 + 2x + 5x2 and B(x) = 1 + 4xR(x) = (3 + 2x + 5x2) * (1 + 4x)R(x) = 3 * 1 + (3 * 4 + 2 * 1)x + (2 * 4 + 5 * 1)x2 + (5 * 4)x3R(x) = 3 + 14x + 13x2 + 20x3[3, 14, 13, 20].Example 2:
Input: poly1 = [1,0,-2], poly2 = [-1]
Output: [-1,0,2]
Explanation:
A(x) = 1 + 0x - 2x2 and B(x) = -1R(x) = (1 + 0x - 2x2) * (-1)R(x) = -1 + 0x + 2x2[-1, 0, 2].Example 3:
Input: poly1 = [1,5,-3], poly2 = [-4,2,0]
Output: [-4,-18,22,-6,0]
Explanation:
A(x) = 1 + 5x - 3x2 and B(x) = -4 + 2x + 0x2R(x) = (1 + 5x - 3x2) * (-4 + 2x + 0x2)R(x) = 1 * -4 + (1 * 2 + 5 * -4)x + (5 * 2 + -3 * -4)x2 + (-3 * 2)x3 + 0x4R(x) = -4 -18x + 22x2 -6x3 + 0x4[-4, -18, 22, -6, 0].
Constraints:
1 <= poly1.length, poly2.length <= 5 * 104-103 <= poly1[i], poly2[i] <= 103poly1 and poly2 contain at least one non-zero coefficient.We can use the Fast Fourier Transform (FFT) to efficiently compute the product of two polynomials. FFT is an efficient algorithm that can compute the product of polynomials in O(n log n) time complexity.
The specific steps are as follows:
m = |A|+|B|-1, and round it up to the nearest power of 2, n, to facilitate divide-and-conquer FFT.invert=False) on both coefficient sequences.invert=True) on the product sequence, and round the real parts to the nearest integer to obtain the final coefficients.The time complexity is O(n log n), and the space complexity is O(n), where n is the length of the polynomials.
Java
C++
Go
TypeScript
Practice Multiply Two Polynomials with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor