3549. Multiply Two Polynomials 🔒
Problem Description
You are given two integer arrays poly1 and poly2, where the element at index i in each array represents the coefficient of x^i 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 x^i in R(x).
Intuition
When multiplying two polynomials, the coefficient for each term in the result is the sum of multiplying pairs of coefficients from the input polynomials whose exponents add up to the same value. A straightforward way to do this is by nested loops, computing every pairwise product, but this becomes slow for large polynomials.
The Fast Fourier Transform (FFT) gives a faster method. By converting the coefficients into the frequency domain using FFT, multiplication of polynomials becomes simple element-wise multiplication. After multiplying, using the inverse FFT brings the result back to the coefficient form. This approach dramatically speeds up the computation for large inputs because FFT works in O(n log n) time instead of O(n^2).
Solution Approach
The solution uses the Fast Fourier Transform (FFT) algorithm to multiply two polynomials efficiently. Here’s the step-by-step approach:
-
Determine Result Length and Padding: The result polynomial will have a length of
poly1.length + poly2.length - 1. To use FFT, round this length up to the next power of two, call thisn. This is because FFT works best when input lengths are a power of two. -
Prepare the Coefficient Arrays: Extend both
poly1andpoly2with zeros so that their lengths matchn. Represent their elements as complex numbers (complextype in Python). -
Forward FFT: For each array, perform the forward FFT transformation (
invert=False). This converts the coefficient representations into the frequency domain. -
Pointwise Multiplication: Multiply corresponding entries from the two transformed arrays. This performs the equivalent of polynomial multiplication in the frequency domain, but much faster than brute force.
-
Inverse FFT: Apply the inverse FFT (
invert=True) to the product array. This transforms the product back from the frequency domain to the coefficient (standard) form. -
Round to Nearest Integer: Due to floating-point precision, the real part of each coefficient may not be exactly an integer. Round each coefficient to the nearest integer.
-
Return the Result: Output the first
mvalues (m = poly1.length + poly2.length - 1) from the array as the final answer.
This approach takes advantage of the fact that convolution in the coefficient domain (what normal polynomial multiplication does) corresponds to pointwise multiplication in the frequency domain, which is achieved through FFT. The time complexity improves to O(n log n) compared to the naïve O(n^2) approach.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose poly1 = [2, 0, 3] and poly2 = [1, 4]. This means:
A(x) = 2 + 0*x + 3*x^2B(x) = 1 + 4*x
The product polynomial has degree 2 + 1 = 3, so the result will have 3 + 1 = 4 coefficients (since result length = poly1.length + poly2.length - 1 = 3 + 2 - 1 = 4).
Step 1: Determine Result Length and Padding
The result length is 4, which is already a power of two. Pad poly1 and poly2 to size 4:
a = [2, 0, 3, 0]b = [1, 4, 0, 0]
Step 2: Prepare Coefficient Arrays
Convert to arrays of complex numbers if using FFT functions.
Step 3: Forward FFT
Apply FFT to both arrays to convert them to the frequency domain:
- Let
fa = FFT(a) - Let
fb = FFT(b)
Step 4: Pointwise Multiplication
Multiply corresponding elements:
fc[i] = fa[i] * fb[i]for eachi
Step 5: Inverse FFT
Perform the inverse FFT to transform fc back to the time domain (coefficients).
Step 6: Round to Nearest Integer
Take the real part of each result coefficient and round to the nearest integer.
Step 7: Return the Result
Output the first 4 coefficients:
Let's do the manual naive multiplication for verification:
(2 + 0x + 3x^2) * (1 + 4x) = 2*1 + 2*4x + 0*1x + 0*4x^2 + 3*1x^2 + 3*4x^3 = 2 + 8x + 3x^2 + 12x^3
So, the result should be [2, 8, 3, 12].
Final output: [2, 8, 3, 12]
This example demonstrates how FFT-based multiplication precisely replicates the result of polynomial multiplication but is efficient for much larger inputs.
Solution Implementation
1import math
2from typing import List
3
4class Solution:
5 def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
6 """
7 Multiplies two polynomials using Fast Fourier Transform (FFT).
8 Args:
9 poly1: Coefficients of the first polynomial (low to high degree).
10 poly2: Coefficients of the second polynomial.
11 Returns:
12 List[int]: Coefficients of the product polynomial.
13 """
14 if not poly1 or not poly2:
15 return []
16
17 # Calculate required size for the FFT (next power of two)
18 result_size = len(poly1) + len(poly2) - 1
19 n = 1
20 while n < result_size:
21 n <<= 1 # Double n until it covers the result size
22
23 # Convert integer coefficients to complex numbers and pad with zeros
24 fa = list(map(complex, poly1)) + [0j] * (n - len(poly1))
25 fb = list(map(complex, poly2)) + [0j] * (n - len(poly2))
26
27 # Forward FFT on both arrays
28 self._fft(fa, invert=False)
29 self._fft(fb, invert=False)
30
31 # Multiply point-wise in frequency domain
32 for i in range(n):
33 fa[i] *= fb[i]
34
35 # Inverse FFT to get the result in time (coefficient) domain
36 self._fft(fa, invert=True)
37
38 # Extract the real part and round to the nearest integer
39 return [int(round(fa[i].real)) for i in range(result_size)]
40
41 def _fft(self, a: List[complex], invert: bool) -> None:
42 """
43 In-place Fast Fourier Transform.
44 Args:
45 a: List of complex input/output values.
46 invert: Whether to perform the inverse FFT.
47 """
48 n = len(a)
49
50 # Bit reversal permutation for in-place reordering
51 j = 0
52 for i in range(1, n):
53 bit = n >> 1
54 while j & bit:
55 j ^= bit
56 bit >>= 1
57 j ^= bit
58 if i < j:
59 a[i], a[j] = a[j], a[i]
60
61 # Iterative FFT implementation
62 length = 2
63 while length <= n:
64 angle = 2 * math.pi / length * (-1 if invert else 1)
65 w_length = complex(math.cos(angle), math.sin(angle))
66 for i in range(0, n, length):
67 w = 1 + 0j
68 mid = i + length // 2
69 for j in range(i, mid):
70 u = a[j]
71 v = a[j + length // 2] * w
72 a[j] = u + v
73 a[j + length // 2] = u - v
74 w *= w_length
75 length <<= 1
76
77 # If computing inverse FFT, divide each value by n
78 if invert:
79 for i in range(n):
80 a[i] /= n
811class Solution {
2 // Multiplies two polynomials using FFT (Fast Fourier Transform)
3 public long[] multiply(int[] poly1, int[] poly2) {
4 // Handle edge case when either polynomial is empty or null
5 if (poly1 == null || poly2 == null || poly1.length == 0 || poly2.length == 0) {
6 return new long[0];
7 }
8
9 int resultLength = poly1.length + poly2.length - 1; // The length of the result array
10 int fftLength = 1;
11
12 // Find the smallest power of 2 >= resultLength for FFT zero-padding
13 while (fftLength < resultLength) {
14 fftLength <<= 1;
15 }
16
17 // Initialize complex arrays for both input polynomials, zero-padded to fftLength
18 Complex[] a = new Complex[fftLength];
19 Complex[] b = new Complex[fftLength];
20 for (int i = 0; i < fftLength; i++) {
21 a[i] = new Complex(i < poly1.length ? poly1[i] : 0, 0);
22 b[i] = new Complex(i < poly2.length ? poly2[i] : 0, 0);
23 }
24
25 // Perform FFT on both arrays (in place)
26 fft(a, false);
27 fft(b, false);
28
29 // Multiply element-wise in frequency domain
30 for (int i = 0; i < fftLength; i++) {
31 a[i] = a[i].mul(b[i]);
32 }
33
34 // Perform inverse FFT to go back to time domain
35 fft(a, true);
36
37 // Round real parts to nearest integer and store in result array
38 long[] result = new long[resultLength];
39 for (int i = 0; i < resultLength; i++) {
40 result[i] = Math.round(a[i].re);
41 }
42
43 return result;
44 }
45
46 // In-place FFT (Cooley-Tukey algorithm). If invert == true, perform inverse FFT.
47 private static void fft(Complex[] array, boolean invert) {
48 int n = array.length;
49
50 // Bit-reversal permutation (reorders elements for in-place transform)
51 for (int i = 1, j = 0; i < n; i++) {
52 int bit = n >>> 1;
53 while ((j & bit) != 0) {
54 j ^= bit;
55 bit >>>= 1;
56 }
57 j ^= bit;
58 if (i < j) {
59 Complex temp = array[i];
60 array[i] = array[j];
61 array[j] = temp;
62 }
63 }
64
65 // Main FFT loop (combining pairs, quadruples, etc.)
66 for (int length = 2; length <= n; length <<= 1) {
67 double angle = 2 * Math.PI / length * (invert ? -1 : 1);
68 Complex wlen = new Complex(Math.cos(angle), Math.sin(angle));
69
70 for (int i = 0; i < n; i += length) {
71 Complex w = new Complex(1, 0);
72 int half = length >>> 1;
73 for (int j = 0; j < half; j++) {
74 Complex u = array[i + j];
75 Complex v = array[i + j + half].mul(w);
76 array[i + j] = u.add(v);
77 array[i + j + half] = u.sub(v);
78 w = w.mul(wlen);
79 }
80 }
81 }
82
83 // Normalize if inverse FFT
84 if (invert) {
85 for (int i = 0; i < n; i++) {
86 array[i].re /= n;
87 array[i].im /= n;
88 }
89 }
90 }
91
92 // Complex number helper class for FFT operations
93 private static final class Complex {
94 double re, im; // Real and imaginary parts
95
96 Complex(double real, double imag) {
97 this.re = real;
98 this.im = imag;
99 }
100
101 // Addition
102 Complex add(Complex other) {
103 return new Complex(this.re + other.re, this.im + other.im);
104 }
105
106 // Subtraction
107 Complex sub(Complex other) {
108 return new Complex(this.re - other.re, this.im - other.im);
109 }
110
111 // Multiplication
112 Complex mul(Complex other) {
113 return new Complex(
114 this.re * other.re - this.im * other.im,
115 this.re * other.im + this.im * other.re
116 );
117 }
118 }
119}
1201#include <vector>
2#include <complex>
3#include <cmath>
4using namespace std;
5
6class Solution {
7 using Complex = complex<double>;
8
9 // Fast Fourier Transform (FFT) implementation
10 void fft(vector<Complex>& a, bool invert) {
11 int n = a.size();
12
13 // Bit-reversal permutation
14 for (int i = 1, j = 0; i < n; ++i) {
15 int bit = n >> 1;
16 while (j & bit) {
17 j ^= bit;
18 bit >>= 1;
19 }
20 j ^= bit;
21 if (i < j) {
22 swap(a[i], a[j]);
23 }
24 }
25
26 // Iterative FFT
27 for (int len = 2; len <= n; len <<= 1) {
28 double angle = 2 * M_PI / len * (invert ? -1 : 1);
29 Complex wlen(cos(angle), sin(angle));
30 for (int i = 0; i < n; i += len) {
31 Complex w(1, 0);
32 for (int j = 0; j < len / 2; ++j) {
33 Complex u = a[i + j];
34 Complex v = a[i + j + len / 2] * w;
35 a[i + j] = u + v;
36 a[i + j + len / 2] = u - v;
37 w *= wlen;
38 }
39 }
40 }
41
42 // If invert is true, divide each value by n
43 if (invert) {
44 for (Complex& x : a) {
45 x /= n;
46 }
47 }
48 }
49
50public:
51 // Multiply two polynomials using FFT and return the resulting coefficients
52 vector<long long> multiply(vector<int>& poly1, vector<int>& poly2) {
53 if (poly1.empty() || poly2.empty()) {
54 return {};
55 }
56
57 // Resultant polynomial size
58 int result_size = poly1.size() + poly2.size() - 1;
59 int n = 1;
60 // Expand n to the next power of two
61 while (n < result_size) {
62 n <<= 1;
63 }
64
65 // Initialize complex vectors for FFT
66 vector<Complex> a(n), b(n);
67 for (int i = 0; i < n; ++i) {
68 a[i] = (i < poly1.size()) ? Complex(poly1[i], 0) : Complex(0, 0);
69 b[i] = (i < poly2.size()) ? Complex(poly2[i], 0) : Complex(0, 0);
70 }
71
72 // Forward FFT
73 fft(a, false);
74 fft(b, false);
75
76 // Point-wise multiplication
77 for (int i = 0; i < n; ++i) {
78 a[i] *= b[i];
79 }
80
81 // Inverse FFT to obtain the coefficients
82 fft(a, true);
83
84 // Round real parts to nearest integer
85 vector<long long> result(result_size);
86 for (int i = 0; i < result_size; ++i) {
87 result[i] = llround(a[i].real());
88 }
89 return result;
90 }
91};
921/**
2 * Multiplies two polynomials using brute-force for small inputs and FFT for large ones.
3 * @param poly1 First polynomial, lowest power first (e.g., [a0, a1, a2] => a0 + a1*x + a2*x^2)
4 * @param poly2 Second polynomial, lowest power first
5 * @returns The product polynomial, lowest power first
6 */
7export function multiply(poly1: number[], poly2: number[]): number[] {
8 const len1 = poly1.length;
9 const len2 = poly2.length;
10 // If any polynomial is empty, return empty result
11 if (!len1 || !len2) return [];
12
13 // Use brute-force for small degree polynomials
14 if (Math.min(len1, len2) <= 64) {
15 const resultLen = len1 + len2 - 1;
16 const result = new Array<number>(resultLen).fill(0);
17 for (let i = 0; i < len1; ++i) {
18 for (let j = 0; j < len2; ++j) {
19 result[i + j] += poly1[i] * poly2[j];
20 }
21 }
22 // Rounding result to handle floating point errors
23 return result.map(v => Math.round(v));
24 }
25
26 // Find the nearest power of two for FFT that is >= (len1 + len2 - 1)
27 let n = 1;
28 const resultLen = len1 + len2 - 1;
29 while (n < resultLen) n <<= 1;
30
31 // Prepare real and imaginary parts for first polynomial
32 const realA = new Float64Array(n);
33 const imagA = new Float64Array(n); // initialized to 0
34 for (let i = 0; i < len1; ++i) realA[i] = poly1[i];
35
36 // Prepare real and imaginary parts for second polynomial
37 const realB = new Float64Array(n);
38 const imagB = new Float64Array(n); // initialized to 0
39 for (let i = 0; i < len2; ++i) realB[i] = poly2[i];
40
41 // FFT on both polynomials
42 fft(realA, imagA, false);
43 fft(realB, imagB, false);
44
45 // Point-wise multiplication of frequency components (complex numbers)
46 for (let i = 0; i < n; ++i) {
47 const aRe = realA[i], aIm = imagA[i];
48 const bRe = realB[i], bIm = imagB[i];
49 // (a + bi) * (c + di) = (ac - bd) + (ad + bc)i
50 realA[i] = aRe * bRe - aIm * bIm;
51 imagA[i] = aRe * bIm + aIm * bRe;
52 }
53
54 // Inverse FFT to get back to coefficient form
55 fft(realA, imagA, true);
56
57 // Extract and round the real part for result, ignore imag part (should be near zero)
58 const result = new Array<number>(resultLen);
59 for (let i = 0; i < resultLen; ++i) {
60 result[i] = Math.round(realA[i]);
61 }
62 return result;
63}
64
65/**
66 * In-place radix-2 FFT (Cooley-Tukey).
67 * @param real Real part, length n (must be power of two)
68 * @param imag Imaginary part, length n (must be power of two)
69 * @param invert Whether to perform inverse FFT
70 */
71function fft(real: Float64Array, imag: Float64Array, invert: boolean): void {
72 const n = real.length;
73
74 // Bit-reversal permutation
75 for (let i = 1, j = 0; i < n; ++i) {
76 let bit = n >> 1;
77 while (j & bit) {
78 j ^= bit;
79 bit >>= 1;
80 }
81 j ^= bit;
82 // Swap only if i < j
83 if (i < j) {
84 [real[i], real[j]] = [real[j], real[i]];
85 [imag[i], imag[j]] = [imag[j], imag[i]];
86 }
87 }
88
89 // Main FFT loop
90 for (let len = 2; len <= n; len <<= 1) {
91 const ang = (2 * Math.PI / len) * (invert ? -1 : 1);
92 const wLenRe = Math.cos(ang);
93 const wLenIm = Math.sin(ang);
94 for (let i = 0; i < n; i += len) {
95 let wRe = 1, wIm = 0;
96 const half = len >> 1;
97 for (let j = 0; j < half; ++j) {
98 const uRe = real[i + j], uIm = imag[i + j];
99 const vRe0 = real[i + j + half], vIm0 = imag[i + j + half];
100 // Complex multiplication: (vRe0 + i*vIm0) * (wRe + i*wIm)
101 const vRe = vRe0 * wRe - vIm0 * wIm;
102 const vIm = vRe0 * wIm + vIm0 * wRe;
103
104 // Update result in place
105 real[i + j] = uRe + vRe;
106 imag[i + j] = uIm + vIm;
107 real[i + j + half] = uRe - vRe;
108 imag[i + j + half] = uIm - vIm;
109
110 // Move to next power of root of unity
111 const nextWRe = wRe * wLenRe - wIm * wLenIm;
112 wIm = wRe * wLenIm + wIm * wLenRe;
113 wRe = nextWRe;
114 }
115 }
116 }
117
118 // For inverse FFT, divide all values by n to normalize
119 if (invert) {
120 for (let i = 0; i < n; ++i) {
121 real[i] /= n;
122 imag[i] /= n;
123 }
124 }
125}
126Time and Space Complexity
The time complexity of the polynomial multiplication code using the Fast Fourier Transform (FFT) is O(n \log n), where n is the sum of the degrees of the input polynomials plus one (specifically, n = len(poly1) + len(poly2) - 1). This is because the FFT operation itself is O(n \log n), and it is performed a constant number of times (forward transform for both polynomials, element-wise multiplication, and an inverse transform).
The space complexity is O(n) since the code creates auxiliary arrays of length up to n (rounded up to the next power of 2 for FFT), and does not require asymptotically more additional memory.
Which type of traversal does breadth first search do?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!