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]) = 2gcd([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