Problem Description

You are given an array of positive integers nums.

The problem introduces a special property called product equivalent. An array arr is product equivalent if it satisfies the equation: prod(arr) == lcm(arr) * gcd(arr)

Where:

• prod(arr) is the product of all elements in the array (multiply all numbers together)
• gcd(arr) is the Greatest Common Divisor of all elements in the array
• lcm(arr) is the Least Common Multiple of all elements in the array

Your task is to find the length of the longest contiguous subarray within nums that has this product equivalent property.

For example, if we have a subarray [a, b, c], it would be product equivalent if: a * b * c == lcm(a, b, c) * gcd(a, b, c)

The solution iterates through all possible subarrays, checking each one to see if it satisfies the product equivalent condition. For each starting position i, it extends the subarray by adding elements one by one, updating the product, GCD, and LCM incrementally. When a subarray satisfies the condition p == g * l, it updates the maximum length found. The optimization if p > max_p: break helps prune the search when the product becomes too large to possibly satisfy the condition.

Intuition

The key insight is understanding when the equation prod(arr) == lcm(arr) * gcd(arr) holds true. This relationship is special because for most arrays, the product is actually larger than lcm * gcd.

Consider what happens with the prime factorizations. For any number, we can express it as a product of prime powers. When calculating:

• The GCD takes the minimum power of each prime across all numbers
• The LCM takes the maximum power of each prime across all numbers
• The product adds up all the powers of each prime

For the equation to hold, the sum of all prime powers (from the product) must equal the sum of the minimum and maximum powers (from gcd * lcm). This happens in special cases, like when we have only one or two distinct numbers, or when the numbers share specific divisibility relationships.

Since we need to find the longest subarray with this property, we must check all possible subarrays. The brute force approach of checking every subarray is actually reasonable here because:

1. We can compute the product, GCD, and LCM incrementally as we extend each subarray, avoiding redundant calculations
2. The product grows exponentially, so we can add an optimization to break early when the product becomes too large

The pruning condition if p > max_p: break is clever - we precompute an upper bound max_p = lcm(*nums) * max(nums) which represents a theoretical maximum for lcm * gcd of any subarray. If our current product exceeds this, there's no way it can equal lcm * gcd for any extension of the current subarray, so we can stop early.

This approach efficiently explores all possibilities while cutting off branches that cannot lead to valid solutions.

Learn more about Math and Sliding Window patterns.

Solution Approach

The solution uses a nested loop approach to check all possible subarrays, with optimizations to make it efficient.

Algorithm Structure:

1. Initialize variables:

   • n = len(nums) to store the array length
   • ans = 0 to track the maximum length found
   • max_p = lcm(*nums) * max(nums) as an upper bound for pruning

2. Outer loop (starting position i): For each position i from 0 to n-1, we consider it as the start of a potential subarray.

3. Initialize tracking variables for each starting position:

   • p = 1 for the running product
   • g = 0 for the running GCD (0 acts as identity for GCD with positive numbers)
   • l = 1 for the running LCM

4. Inner loop (extending the subarray): For each position j from i to n-1:

   • Update the product: p *= nums[j]
   • Update the GCD: g = gcd(g, nums[j])
   • Update the LCM: l = lcm(l, nums[j])

   The incremental computation is key here - instead of recalculating from scratch for each subarray, we build upon the previous values.

5. Check the product equivalent condition: If p == g * l, we found a valid subarray from index i to j. Update the answer: ans = max(ans, j - i + 1)

6. Pruning optimization: If p > max_p, break from the inner loop. Since the product only increases as we extend the subarray, and it's already exceeded the maximum possible value of lcm * gcd, no further extensions can be valid.

Why this works:

• The GCD of a subarray can only decrease or stay the same as we add more elements
• The LCM typically increases as we add more elements
• The product always increases (since all numbers are positive)
• The precomputed max_p gives us an upper bound because:
  • The LCM of any subarray ≤ LCM of the entire array
  • The GCD of any subarray ≤ maximum element in the array

This ensures we explore all potentially valid subarrays while avoiding unnecessary computation when the product grows too large.

Example Walkthrough

Let's walk through the solution with nums = [6, 12, 3].

Initial Setup:

• n = 3
• ans = 0 (tracks maximum length)
• max_p = lcm(6, 12, 3) * max(6, 12, 3) = 12 * 12 = 144 (upper bound for pruning)

Starting from index i = 0:

Subarray [6] (i=0, j=0):

• p = 1 * 6 = 6
• g = gcd(0, 6) = 6
• l = lcm(1, 6) = 6
• Check: 6 == 6 * 6? No (6 ≠ 36)
• Check pruning: 6 > 144? No, continue

Subarray [6, 12] (i=0, j=1):

• p = 6 * 12 = 72
• g = gcd(6, 12) = 6
• l = lcm(6, 12) = 12
• Check: 72 == 6 * 12? Yes! ✓
• Update: ans = max(0, 1 - 0 + 1) = 2
• Check pruning: 72 > 144? No, continue

Subarray [6, 12, 3] (i=0, j=2):

• p = 72 * 3 = 216
• g = gcd(6, 3) = 3
• l = lcm(12, 3) = 12
• Check: 216 == 3 * 12? No (216 ≠ 36)
• Check pruning: 216 > 144? Yes, break inner loop

Starting from index i = 1:

Subarray [12] (i=1, j=1):

• p = 1 * 12 = 12
• g = gcd(0, 12) = 12
• l = lcm(1, 12) = 12
• Check: 12 == 12 * 12? No (12 ≠ 144)
• Check pruning: 12 > 144? No, continue

Subarray [12, 3] (i=1, j=2):

• p = 12 * 3 = 36
• g = gcd(12, 3) = 3
• l = lcm(12, 3) = 12
• Check: 36 == 3 * 12? Yes! ✓
• Update: ans = max(2, 2 - 1 + 1) = 2
• Check pruning: 36 > 144? No, continue

Starting from index i = 2:

Subarray [3] (i=2, j=2):

• p = 1 * 3 = 3
• g = gcd(0, 3) = 3
• l = lcm(1, 3) = 3
• Check: 3 == 3 * 3? No (3 ≠ 9)

Final Result: The longest product equivalent subarray has length 2, corresponding to subarrays [6, 12] and [12, 3].

The key observations from this walkthrough:

1. The incremental computation saves time - we build upon previous products, GCDs, and LCMs
2. The pruning optimization (p > max_p) helps us skip impossible extensions early
3. The equation prod = gcd * lcm holds for special cases where the numbers have particular divisibility relationships (like 6 and 12, or 12 and 3)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × (log M + k)) where n is the length of the array, M is the maximum value in the array, and k is the average number of elements in each subarray.

• The outer loop runs n times for each starting position i
• The inner loop runs at most n times for each ending position j
• For each iteration of the inner loop:
  • Product calculation: O(1)
  • GCD calculation: O(log M) where M is the maximum value
  • LCM calculation: O(log M)
• The initial LCM calculation lcm(*nums) takes O(n × log M) time
• The pruning condition if p > max_p: break helps reduce the actual iterations, but worst-case remains O(n²)

Overall: O(n × log M) + O(n² × log M) = O(n² × log M)

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space for variables: ans, max_p, p, g, l, i, j
• The gcd and lcm functions use O(1) space (iterative implementation)
• The initial lcm(*nums) calculation might use O(n) space temporarily for the unpacking operation, but this depends on the implementation
• No additional data structures are used

Overall space complexity: O(1) auxiliary space (not counting the input array)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Products

The most critical pitfall is that the product of array elements can grow exponentially large. For example, with an array like [10, 20, 30, 40, 50], the product quickly exceeds typical integer limits. In Python, while integers can be arbitrarily large, the computation becomes inefficient and the comparison p == g * l might fail due to numerical issues in other languages.

Solution:

• Use the pruning optimization with max_product_bound to stop early when products become too large
• Consider using logarithms for comparison if dealing with very large numbers: log(p) ≈ log(g) + log(l)
• In languages with fixed integer sizes, use appropriate data types (e.g., long long in C++)

2. Incorrect GCD Initialization

A common mistake is initializing current_gcd = nums[i] at the start of each subarray. This seems logical but breaks the incremental computation pattern and requires special handling for single-element subarrays.

Solution: Initialize current_gcd = 0. The mathematical property gcd(0, x) = x for any positive integer x makes this work seamlessly for all subarray sizes.

3. Computing LCM of Large Numbers

The LCM can grow very quickly, especially with numbers that share few common factors. Computing lcm(a, b) using the formula (a * b) / gcd(a, b) can cause overflow even in intermediate calculations.

Solution:

• Use the built-in lcm function which handles this properly
• If implementing manually, compute as a // gcd(a, b) * b to avoid overflow
• For multiple numbers, compute LCM incrementally rather than all at once

4. Inefficient Max Product Bound Calculation

Computing lcm(*nums) for the entire array can be extremely expensive or cause overflow when the array is large or contains many coprime numbers.

Solution:

# Instead of lcm(*nums) * max(nums), use a more conservative bound:
max_product_bound = float('inf')  # Or use a reasonable upper limit
# Alternatively, compute it incrementally with early stopping:
temp_lcm = 1
for num in nums:
    temp_lcm = lcm(temp_lcm, num)
    if temp_lcm > 10**18:  # Some reasonable threshold
        max_product_bound = float('inf')
        break
else:
    max_product_bound = temp_lcm * max(nums)

5. Missing Edge Cases

Not handling arrays with single elements or when all elements are identical can lead to incorrect results.

Solution:

• Single element subarrays always satisfy the property (since x = gcd(x) * lcm(x) = x * x / x = x)
• Arrays where all elements are the same number k satisfy the property for any length (since k^n = k * k^(n-1))
• Ensure the algorithm handles these cases naturally through the incremental computation