Maximum subarray with equal products

Array Math Sliding Window Enumeration Number Theory

46.5% acceptance

Feb 25, 2026

101

You are given an array of positive integers nums. An array arr is called product equivalent if prod(arr) == lcm(arr) * gcd(arr), where: prod(arr) is the product of all elements of arr. gcd(arr) is the GCD of all elements of arr. lcm(arr) is the LCM of all elements of arr. Return the length of the longest product equivalent subarray of nums.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_length(nums: Vec<i32>) -> i32 {
    let n = nums.len();

    fn gcd(a: i64, b: i64) -> i64 {
      if b == 0 { a } else { gcd(b, a % b) }
    }
    fn lcm(a: i64, b: i64) -> i64 {
      a / gcd(a, b) * b
    }

    let mut ans = 0i32;
    for l in 0..n {
      let mut prod: i64 = 1;
      let mut g = nums[l] as i64;
      let mut lc = nums[l] as i64;
      for r in l..n {
        let v = nums[r] as i64;
        lc = lcm(lc, v);
        g = gcd(g, v);
        prod = prod.saturating_mul(v);
        let target = g * lc;
        if prod == target {
          let len = (r - l + 1) as i32;
          if len > ans {
            ans = len;
          }
        }
        // prod only grows; target <= lcm(1..10)*10 = 25200
        if prod > 25200 {
          break;
        }
      }
    }
    ans
  }
}