Maximum Subarray With Equal Products | Problem Explanation and Solution Approach

 In this blog post, we will discuss an intriguing problem from LeetCode Weekly Contest 431: "Maximum Subarray With Equal Products." We will break down the problem statement, understand the logic behind the solution, and explore a working implementation in C++.

---

Problem Statement

You are given an array of positive integers nums.

An array arr is called product equivalent if:

$$\text{prod(arr)} = \text{lcm(arr)} \times \text{gcd(arr)}$$

Where:

1. prod(arr): The product of all elements in arr.
2. gcd(arr): The greatest common divisor of all elements in arr.
3. lcm(arr): The least common multiple of all elements in arr.

Your task is to return the length of the longest product equivalent subarray in nums.

A subarray is defined as a contiguous non-empty sequence of elements within an array.

---

Examples

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].
For this subarray:

• Product = 1 * 2 * 1 * 1 * 1 = 2
• GCD = 1
• LCM = 2 Since prod = gcd * lcm, the subarray is valid, and its length is 5.

---

Example 2:

Input: nums = [2, 3, 4, 5, 6]
Output: 3
Explanation:
The longest product equivalent subarray is [3, 4, 5].
For this subarray:

• Product = 3 * 4 * 5 = 60
• GCD = 1
• LCM = 60 Since prod = gcd * lcm, the subarray is valid, and its length is 3.

---

Example 3:

Input: nums = [1, 2, 3, 1, 4, 5, 1]
Output: 5
Explanation:
The longest product equivalent subarray is [2, 3, 1, 4, 5].
For this subarray:

• Product = 120
• GCD = 1
• LCM = 120 Since prod = gcd * lcm, the subarray is valid, and its length is 5.

---

Constraints

• $2 \leq \text{nums.length} \leq 100$
• $1 \leq \text{nums[i]} \leq 10$

---

Solution Approach

This problem involves three mathematical concepts:

1. Product (prod): Multiplying all elements in a subarray.
2. Greatest Common Divisor (gcd): The largest integer that divides all elements of a subarray.
3. Least Common Multiple (lcm): The smallest integer that is a multiple of all elements in a subarray.

The condition prod(arr) == lcm(arr) * gcd(arr) simplifies into a computational problem where we need to calculate the GCD and LCM iteratively for each subarray while avoiding overflow issues.

---

Steps to Solve

1. Iterate Through All Subarrays:

   • Start with each index $i$ as the starting point of a subarray.
   • Extend the subarray to index $j$ and calculate the product, GCD, and LCM dynamically.

2. Check the Condition:

   • For each subarray, check if $\text{prod(arr)} = \text{gcd(arr)} \times \text{lcm(arr)}$. If true, update the maximum subarray length.

3. Prevent Overflow:

   • Since the product of the elements can grow exponentially, ensure the product does not exceed the limits of a 64-bit integer.

4. Optimize Calculations:

   • Use the formula $\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$ to calculate LCM efficiently.

---

C++ Code Implementation

Here’s the complete C++ code for solving the problem:

class Solution

{

public:

    int maxLength(vector<int> &nums)

    {

        int n = nums.size();

        int maxLength = 0;

        for (int i = 0; i < n; ++i)

        {

            long long prod = 1;

            int currentGCD = 0;

            long long currentLCM = 1;

            for (int j = i; j < n; ++j)

            {

                if (prod > LLONG_MAX / nums[j])

                    break;

                prod *= nums[j];

                currentGCD = (j == i) ? nums[j] : gcd(currentGCD, nums[j]);

                currentLCM = (j == i) ? nums[j] : (currentLCM / gcd(currentLCM, nums[j])) * nums[j];

                if (prod == currentGCD * currentLCM)

                {

                    maxLength = max(maxLength, j - i + 1);

                }

            }

        }

        return maxLength;

    }

};

Key Points

1. GCD and LCM Calculation:

   • GCD is calculated using the built-in gcd function in C++.
   • LCM is calculated using the formula: $$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$$

2. Overflow Prevention:

   • If the product exceeds the maximum limit of a 64-bit integer (LLONG_MAX), break the loop.

3. Time Complexity:

   • The algorithm runs in $O(n^2)$, where $n$ is the length of the array. For each subarray, GCD and LCM are calculated efficiently.

4. Space Complexity:

   • The solution uses only scalar variables, resulting in $O(1)$ additional space.

---

Example Walkthrough

Input: nums = [1, 2, 1, 2, 1, 1, 1]

• Subarray [1, 2, 1, 1, 1] satisfies the condition.
• Length = 5.

Input: nums = [2, 3, 4, 5, 6]

• Subarray [3, 4, 5] satisfies the condition.
• Length = 3.

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

• Subarray [2, 3, 1, 4, 5] satisfies the condition.
• Length = 5.