Maximum Subarray With Equal Products - Practice Coding Problems

Maximum Subarray With Equal Products - Problem

Array Math Sliding Window Enumeration Number Theory Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4]

› Output: 1

💡 Note: Only single-element subarrays are product equivalent. For [1]: product=1, gcd=1, lcm=1, so 1 = 1×1 ✓. For [1,2]: product=2, gcd=1, lcm=2, so 2 ≠ 1×2 ✗.

Example 2 — Multiple Equal Elements

$ Input: nums = [6,6]

› Output: 2

💡 Note: The subarray [6,6] is product equivalent: product=36, gcd=6, lcm=6, so 36 = 6×6 ✓. Length is 2.

Example 3 — Single Element Only

$ Input: nums = [2,4,8]

› Output: 1

💡 Note: Each single element works: [2] has 2=2×1, [4] has 4=4×1, [8] has 8=8×1. But [2,4] has product=8, gcd=2, lcm=4, so 8 = 2×4 ✓, giving length 2.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of positive integers

Check Condition

For each subarray, verify if product equals GCD × LCM

Find Maximum

Return length of longest valid subarray

Key Takeaway

🎯 Key Insight: Product equals GCD×LCM only when elements have special mathematical relationships, often when they're identical or share common factors

Asked in

G Google 12 M Microsoft 8

The key insight is that product equals GCD×LCM only in special mathematical cases, typically when elements are identical or have specific divisibility relationships. Best approach uses optimized enumeration with early termination. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Early Mathematical Insights	O(n²)	O(1)	Use mathematical properties to avoid redundant calculations and identify patterns
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and verify the product equivalent condition

Optimized - Early Mathematical Insights — Algorithm Steps

Step 1: Start with each element as a potential starting point
Step 2: Extend subarrays incrementally, updating GCD, LCM, and product
Step 3: Stop extending when mathematical conditions make success impossible

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Point

Begin with each element as starting point

Extend & Calculate

Extend subarray incrementally, updating GCD, LCM, product

Early Stop

Terminate when product grows too large compared to GCD×LCM

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, int b) {
    return a * b / gcd(a, b);
}

int solution(int* nums, int numsSize) {
    int maxLength = 1;
    
    for (int i = 0; i < numsSize; i++) {
        int currentGcd = nums[i];
        long long currentLcm = nums[i];
        long long product = nums[i];
        
        for (int j = i; j < numsSize; j++) {
            if (j > i) {
                currentGcd = gcd(currentGcd, nums[j]);
                currentLcm = lcm(currentLcm, nums[j]);
                product *= nums[j];
            }
            
            if (product == (long long)currentGcd * currentLcm) {
                int length = j - i + 1;
                if (length > maxLength) {
                    maxLength = length;
                }
            }
            
            if (product > (long long)currentGcd * currentLcm * 1000) {
                break;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops but with optimized calculations and early stopping

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses variables to track current GCD, LCM, product, and maximum length

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Early Mathematical Insights — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler