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 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

  • 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 }

All Problems

All Solutions