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.

Example 1

1
2
3
4
5

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

1
2
3
4

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

Example 3

1
2

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

Constraints

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

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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; }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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; }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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.