Maximum Subarray With Equal Products

Problem

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.

Examples

Example 1

Input: nums = [1,2,1,2,1,1,1]
Output: 5
Explanation:  
The longest product equivalent subarray is `[1, 2, 1, 1, 1]`, where `prod([1,
2, 1, 1, 1]) = 2`, `gcd([1, 2, 1, 1, 1]) = 1`, and `lcm([1, 2, 1, 1, 1]) = 2`.

Example 2

Input: nums = [2,3,4,5,6]
Output: 3
Explanation:  
The longest product equivalent subarray is `[3, 4, 5].`

Example 3

Input: nums = [1,2,3,1,4,5,1]
Output: 5

Constraints

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 10

Solution

Method 1 – Sliding Window with GCD and LCM Tracking

Intuition

A subarray is product equivalent if prod(arr) == lcm(arr) * gcd(arr). For positive integers, this holds if and only if all elements are equal or all are 1. We can use a sliding window to check for the longest such subarray.

Approach

1. For each possible starting index, expand the window to the right as long as the GCD and LCM of the window satisfy prod == gcd * lcm.
2. Use math.gcd and lcm functions to update GCD and LCM efficiently.
3. Track the maximum window length found.

Code

C++

class Solution {
public:
    int maxProductEquivalentSubarray(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        for (int i = 0; i < n; ++i) {
            long long prod = 1, g = nums[i], l = nums[i];
            for (int j = i; j < n; ++j) {
                prod *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                if (prod == g * l) ans = max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
    long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
    long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
};

Go

func gcd(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
func lcm(a, b int) int { return a / gcd(a, b) * b }
func maxProductEquivalentSubarray(nums []int) int {
    n, ans := len(nums), 1
    for i := 0; i < n; i++ {
        prod, g, l := 1, nums[i], nums[i]
        for j := i; j < n; j++ {
            prod *= nums[j]
            g = gcd(g, nums[j])
            l = lcm(l, nums[j])
            if prod == g*l {
                if j-i+1 > ans { ans = j-i+1 }
            } else { break }
        }
    }
    return ans
}

Java

class Solution {
    public int maxProductEquivalentSubarray(int[] nums) {
        int n = nums.length, ans = 1;
        for (int i = 0; i < n; ++i) {
            long prod = 1, g = nums[i], l = nums[i];
            for (int j = i; j < n; ++j) {
                prod *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                if (prod == g * l) ans = Math.max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
    long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
    long lcm(long a, long b) { return a / gcd(a, b) * b; }
}

Kotlin

class Solution {
    fun maxProductEquivalentSubarray(nums: IntArray): Int {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        fun lcm(a: Int, b: Int): Int = a / gcd(a, b) * b
        val n = nums.size
        var ans = 1
        for (i in 0 until n) {
            var prod = 1L; var g = nums[i]; var l = nums[i]
            for (j in i until n) {
                prod *= nums[j]
                g = gcd(g, nums[j])
                l = lcm(l, nums[j])
                if (prod == g.toLong() * l) ans = maxOf(ans, j - i + 1)
                else break
            }
        }
        return ans
    }
}

Python

class Solution:
    def maxProductEquivalentSubarray(self, nums: list[int]) -> int:
        from math import gcd
        def lcm(a, b): return a * b // gcd(a, b)
        n = len(nums)
        ans = 1
        for i in range(n):
            prod, g, l = 1, nums[i], nums[i]
            for j in range(i, n):
                prod *= nums[j]
                g = gcd(g, nums[j])
                l = lcm(l, nums[j])
                if prod == g * l:
                    ans = max(ans, j - i + 1)
                else:
                    break
        return ans

Rust

impl Solution {
    pub fn max_product_equivalent_subarray(nums: Vec<i32>) -> i32 {
        fn gcd(mut a: i64, mut b: i64) -> i64 { while b != 0 { let t = b; b = a % b; a = t; } a }
        fn lcm(a: i64, b: i64) -> i64 { a / gcd(a, b) * b }
        let n = nums.len();
        let mut ans = 1;
        for i in 0..n {
            let (mut prod, mut g, mut l) = (1i64, nums[i] as i64, nums[i] as i64);
            for j in i..n {
                prod *= nums[j] as i64;
                g = gcd(g, nums[j] as i64);
                l = lcm(l, nums[j] as i64);
                if prod == g * l {
                    ans = ans.max((j - i + 1) as i32);
                } else { break; }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxProductEquivalentSubarray(nums: number[]): number {
        function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }
        function lcm(a: number, b: number): number { return a / gcd(a, b) * b; }
        const n = nums.length;
        let ans = 1;
        for (let i = 0; i < n; ++i) {
            let prod = 1, g = nums[i], l = nums[i];
            for (let j = i; j < n; ++j) {
                prod *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                if (prod === g * l) ans = Math.max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2 log M), where n is the length of nums and M is the maximum value in nums. Each subarray is checked, and GCD/LCM are computed in log M time.
• 🧺 Space complexity: O(1), only a few variables are used.