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).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 this n. This is because FFT works best when input lengths are a power of two.
Prepare the Coefficient Arrays: Extend both poly1 and poly2 with zeros so that their lengths match n. Represent their elements as complex numbers (complex type 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 m values (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 Evaluator

Example Walkthrough

Suppose poly1 = [2, 0, 3] and poly2 = [1, 4]. This means:

A(x) = 2 + 0*x + 3*x^2
B(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 each i

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
81

1class 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}
120

1#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};
92

1/**
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}
126

Time 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: