Multiply two polynomials

Array Math

59.6% acceptance

Mar 31, 2026

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

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn multiply(poly1: Vec<i32>, poly2: Vec<i32>) -> Vec<i64> {
    // Use FFT (NTT) for O(n log n) polynomial multiplication.
    // But given constraints (n up to 5*10^4, coefficients up to 10^3),
    // the result values can be up to 5*10^4 * 10^3 * 10^3 = 5*10^10 which fits i64.
    // For correctness, use standard NTT or just do direct convolution since n is manageable.
    // n1 * n2 up to 5*10^4 * 5*10^4 = 2.5*10^9 which is too large for O(n*m).
    // Need FFT/NTT.
    
    let n = poly1.len();
    let m = poly2.len();
    let result_len = n + m - 1;
    
    // Use f64 FFT
    let mut size = 1;
    while size < result_len { size <<= 1; }
    size <<= 1; // double for safety
    
    let mut fa: Vec<(f64, f64)> = vec![(0.0, 0.0); size];
    let mut fb: Vec<(f64, f64)> = vec![(0.0, 0.0); size];
    
    for i in 0..n { fa[i].0 = poly1[i] as f64; }
    for i in 0..m { fb[i].0 = poly2[i] as f64; }
    
    fn fft(a: &mut [(f64, f64)], invert: bool) {
      let n = a.len();
      if n == 1 { return; }
      
      // Bit-reversal permutation
      let mut j = 0usize;
      for i in 1..n {
        let mut bit = n >> 1;
        while j & bit != 0 {
          j ^= bit;
          bit >>= 1;
        }
        j ^= bit;
        if i < j { a.swap(i, j); }
      }
      
      let mut len = 2;
      while len <= n {
        let ang = 2.0 * std::f64::consts::PI / len as f64 * if invert { -1.0 } else { 1.0 };
        let wlen = (ang.cos(), ang.sin());
        let half = len / 2;
        for i in (0..n).step_by(len) {
          let mut w = (1.0, 0.0);
          for jj in 0..half {
            let u = a[i + jj];
            let v = (
              a[i + jj + half].0 * w.0 - a[i + jj + half].1 * w.1,
              a[i + jj + half].0 * w.1 + a[i + jj + half].1 * w.0,
            );
            a[i + jj] = (u.0 + v.0, u.1 + v.1);
            a[i + jj + half] = (u.0 - v.0, u.1 - v.1);
            w = (w.0 * wlen.0 - w.1 * wlen.1, w.0 * wlen.1 + w.1 * wlen.0);
          }
        }
        len <<= 1;
      }
      
      if invert {
        let inv_n = 1.0 / n as f64;
        for x in a.iter_mut() {
          x.0 *= inv_n;
          x.1 *= inv_n;
        }
      }
    }
    
    fft(&mut fa, false);
    fft(&mut fb, false);
    
    for i in 0..size {
      let (a, b) = (fa[i], fb[i]);
      fa[i] = (a.0 * b.0 - a.1 * b.1, a.0 * b.1 + a.1 * b.0);
    }
    
    fft(&mut fa, true);
    
    (0..result_len).map(|i| fa[i].0.round() as i64).collect()
  }
}