Skip to content

3411. Maximum Subarray With Equal Products

SourceWeekly Contest 431 Q1DifficultyEasyRating1443

Description

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:

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

Solutions

Solution 1

Thinking

The product equaling \(\gcd\cdot\operatorname{lcm}\) is an algebraic test on a subarray. With \(n\le 100\) and values \(\le 10\), we can enumerate every subarray while maintaining product, GCD, and LCM.

The product grows quickly. Once it exceeds \(\operatorname{lcm}(\textit{nums})\cdot\max(\textit{nums})\), a longer suffix cannot satisfy the identity, so the inner loop should stop.

We fix the left end \(i\), extend rightward updating \(p\), \(g\), and \(l\), record the length when \(p=g\cdot l\), and break when \(p\) is already too large.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maxLength(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        max_p = lcm(*nums) * max(nums)
        for i in range(n):
            p, g, l = 1, 0, 1
            for j in range(i, n):
                p *= nums[j]
                g = gcd(g, nums[j])
                l = lcm(l, nums[j])
                if p == g * l:
                    ans = max(ans, j - i + 1)
                if p > max_p:
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int maxLength(int[] nums) {
        int mx = 0, ml = 1;
        for (int x : nums) {
            mx = Math.max(mx, x);
            ml = lcm(ml, x);
        }
        int maxP = ml * mx;
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int p = 1, g = 0, l = 1;
            for (int j = i; j < n; ++j) {
                p *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                if (p == g * l) {
                    ans = Math.max(ans, j - i + 1);
                }
                if (p > maxP) {
                    break;
                }
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private int lcm(int a, int 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
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maxLength(vector<int>& nums) {
        int mx = 0, ml = 1;
        for (int x : nums) {
            mx = max(mx, x);
            ml = lcm(ml, x);
        }

        long long maxP = (long long) ml * mx;
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            long long p = 1, g = 0, l = 1;
            for (int j = i; j < n; ++j) {
                p *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);

                if (p == g * l) {
                    ans = max(ans, j - i + 1);
                }
                if (p > maxP) {
                    break;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func maxLength(nums []int) int {
    mx, ml := 0, 1
    for _, x := range nums {
        mx = max(mx, x)
        ml = lcm(ml, x)
    }
    maxP := ml * mx
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        p, g, l := 1, 0, 1
        for j := i; j < n; j++ {
            p *= nums[j]
            g = gcd(g, nums[j])
            l = lcm(l, nums[j])
            if p == g*l {
                ans = max(ans, j-i+1)
            }
            if p > maxP {
                break
            }
        }
    }
    return ans
}

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
}

Comments