Welcome to Subscribe On Youtube
3411. Maximum Subarray With Equal Products
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 ofarr
.gcd(arr)
is the GCD of all elements ofarr
.lcm(arr)
is the LCM of all elements ofarr
.
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
-
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; } }
-
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; } };
-
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
-
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 }