We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Subarray With Equal Products

Number: 3702

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, find the length of the longest contiguous subarray that is "product equivalent". A subarray is product equivalent if the product of its elements is equal to the product of its greatest common divisor (GCD) and its least common multiple (LCM).

Key Insights

  • For any two positive integers, it is a well-known identity that a * b = gcd(a, b) * lcm(a, b), so every subarray of length 2 will always be product equivalent.
  • For subarrays of length 1, note that the identity only holds if the number is 1; because for any number x ≠ 1 the equality x != x*x.
  • For subarrays of length ≥ 3, the equality may or may not hold. A brute-force enumeration is acceptable given that the maximum array length is only 100.
  • The challenge is to correctly calculate the product, GCD, and LCM for each subarray. Although the product may grow large, the small input constraints (numbers ≤ 10) mean that even a brute-force calculation (using Python’s big integers, for example) is feasible.
  • When computing LCM iteratively, remember that lcm(a, b) = a * b / gcd(a, b).

Space and Time Complexity

Time Complexity: O(n^2 * log(max(nums))) where n is the length of the array (subarray enumeration multiplied by cost of GCD/LCM operations) Space Complexity: O(1) extra space (ignoring the space needed for the output result)

Solution

The solution enumerates all possible contiguous subarrays. For each subarray, we compute:

  1. The product of all elements.
  2. The GCD of all elements.
  3. The LCM of all elements (by iteratively applying lcm on pairs). Then, we check if product == gcd * lcm for that subarray. If so, we update the maximum subarray length. Special care is taken with single-element subarrays, since the equality only holds when that single element is 1.

We use helper functions for GCD and LCM calculations. The algorithm is implemented in a brute-force manner as the constraints allow it, and the clarity outweighs the need for additional optimizations.

Code Solutions

# Python solution for Maximum Subarray With Equal Products

import math
from typing import List

def gcd_of_list(nums: List[int]) -> int:
    # Compute GCD for a list of numbers
    current_gcd = nums[0]
    for num in nums[1:]:
        current_gcd = math.gcd(current_gcd, num)
    return current_gcd

def lcm(a: int, b: int) -> int:
    # Compute LCM of two numbers
    return a * b // math.gcd(a, b)

def lcm_of_list(nums: List[int]) -> int:
    # Compute LCM for a list of numbers
    current_lcm = nums[0]
    for num in nums[1:]:
        current_lcm = lcm(current_lcm, num)
    return current_lcm

def maxProductEquivalentSubarray(nums: List[int]) -> int:
    n = len(nums)
    max_length = 0
    # Enumerate every possible subarray
    for i in range(n):
        curr_product = 1
        curr_gcd = 0  # To be updated iteratively
        curr_lcm = 1
        for j in range(i, n):
            num = nums[j]
            curr_product *= num  # Update the product
            # Update gcd; if starting a subarray, set gcd=num; else, use math.gcd
            curr_gcd = num if j == i else math.gcd(curr_gcd, num)
            # Update lcm; if subarray starts, lcm is the number; else, compute with previous lcm
            curr_lcm = num if j == i else lcm(curr_lcm, num)
            # Check the special condition for a single-element subarray
            if i == j and num != 1:
                # For a single element x, product==x and gcd==x and lcm==x, hence condition becomes x == x*x. 
                # This is true only when x==1.
                continue
            # If condition is satisfied, update max_length
            if curr_product == curr_gcd * curr_lcm:
                max_length = max(max_length, j - i + 1)
    return max_length

# Example usage:
nums_example = [1,2,1,2,1,1,1]
print(maxProductEquivalentSubarray(nums_example))  # Output should be 5
← Back to All Questions