3411. Maximum Subarray With Equal Products

EasyArrayMathEnumerationNumber TheorySliding Window

Problem Description

You are given an array of positive integers nums. An array arr is deemed product equivalent if the condition prod(arr) == lcm(arr) * gcd(arr) holds true, where prod(arr) represents the product of all elements in arr, gcd(arr) is the greatest common divisor of all elements, and lcm(arr) is the least common multiple of all elements in arr. The task is to find and return the length of the longest product equivalent subarray within the given array nums.

Intuition

To solve the problem, the core idea is to examine all possible subarrays and check if each satisfies the given condition prod(arr) == lcm(arr) * gcd(arr). The approach involves two nested loops to generate every possible subarray. For each subarray, calculate the product, gcd, and lcm of its elements. Compare the product against the product of the lcm and gcd. If they match, update the length of the longest valid subarray found so far. We incorporate an early exit strategy: if the current product exceeds the maximum possible product (defined as lcm(*nums) * max(nums)), skip further computation for efficiency.

Learn more about Math and Sliding Window patterns.

Solution Approach

The solution approach implemented in the solution code involves a brute force technique facilitated by nested loops, whereby each potential subarray of nums is examined:

Initialization Steps:
- Determine the length of the input array nums and store it in n.
- Initialize the variable ans to keep track of the maximum length of a product equivalent subarray discovered.
- Calculate max_p, which serves as an upper bound for product comparisons. It is computed as lcm(*nums) * max(nums).
Generate Subarrays:
- Use a pair of nested loops where the outer loop iterates i over the starting indices of subarrays and the inner loop iterates j over the ending indices.
Calculating Properties for Each Subarray:
- Initialize p (product of the subarray's elements), g (gcd of the elements), and l (lcm of the elements) at the start of the subarray.
- As each new element at position j is added to the subarray:
  - Update p by multiplying it with the new element.
  - Update g by recalculating the gcd of g with the new element.
  - Update l by recalculating the lcm of l with the new element.
Check Product Equivalence:
- If p equals g * l, then the subarray from index i to j is product equivalent. Update ans accordingly to reflect the new longest subarray length if applicable.
- If p exceeds max_p, break the inner loop early, avoiding unnecessary calculations for subarrays starting at index i.
Return Result:
- Finally, return ans which holds the length of the longest product equivalent subarray found.

The solution makes strategic use of mathematical functions gcd and lcm, combined with iteration to explore subarrays. This comprehensive approach ensures efficient checking of each subarray's product equivalence.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose nums = [2, 4, 3].

Step-by-Step Walkthrough:

Initialization:
- Length of nums (n) is 3.
- ans is initialized to 0 to track the maximum length of a product equivalent subarray found.
- Calculate max_p, where max_p = lcm(*nums) * max(nums).
  - lcm(2, 4, 3) = 12 and max(nums) = 4, thus max_p = 48.
Generate Subarrays:
- For each subarray, check product equivalence. Here are the specifics:
Subarray starting at index 0:
- i = 0
  - j = 0: Subarray = [2]
    - p = 2
    - g = gcd([2]) = 2
    - l = lcm([2]) = 2
    - Check if p == g * l ⇒ 2 == 2 * 2 (False)
  - j = 1: Subarray = [2, 4]
    - p = 2 * 4 = 8
    - g = gcd(2, 4) = 2
    - l = lcm(2, 4) = 4
    - Check if p == g * l ⇒ 8 == 2 * 4 (True)
    - Update ans to max(ans, j - i + 1) = max(0, 2) = 2
  - j = 2: Subarray = [2, 4, 3]
    - p = 8 * 3 = 24
    - g = gcd(2, 4, 3) = 1
    - l = lcm(2, 4, 3) = 12
    - Check if p == g * l ⇒ 24 == 1 * 12 (False)
    - Since 24 < max_p (48), iteration continues.
Subarray starting at index 1:
- i = 1
  - j = 1: Subarray = [4]
    - p = 4
    - g = gcd([4]) = 4
    - l = lcm([4]) = 4
    - Check if p == g * l ⇒ 4 == 4 * 4 (False)
  - j = 2: Subarray = [4, 3]
    - p = 4 * 3 = 12
    - g = gcd(4, 3) = 1
    - l = lcm(4, 3) = 12
    - Check if p == g * l ⇒ 12 == 1 * 12 (True)
    - Update ans to max(ans, j - i + 1) = max(2, 2) = 2
Subarray starting at index 2:
- i = 2
  - j = 2: Subarray = [3]
    - p = 3
    - g = gcd([3]) = 3
    - l = lcm([3]) = 3
    - Check if p == g * l ⇒ 3 == 3 * 3 (False)
Return Result:
- The longest product equivalent subarray found has length 2. So, the result is 2.

Solution Implementation

1from math import gcd
2from typing import List
3
4class Solution:
5    def maxLength(self, nums: List[int]) -> int:
6        # Get the number of elements in the list
7        num_length = len(nums)
8        max_length = 0
9
10        # Calculate the maximum product possible, to use as a stopping condition
11        max_possible_product = self.lcm_of_list(nums) * max(nums)
12
13        # Iterate over each starting point in the list
14        for start in range(num_length):
15            product, current_gcd, current_lcm = 1, 0, 1
16
17            # Iterate over each endpoint for the current starting point
18            for end in range(start, num_length):
19                # Update the product of elements
20                product *= nums[end]
21                # Update the GCD for the current range
22                current_gcd = gcd(current_gcd, nums[end])
23                # Update the LCM for the current range
24                current_lcm = self.lcm(current_lcm, nums[end])
25
26                # Check if the condition p == g * l is met
27                if product == current_gcd * current_lcm:
28                    # Update the maximum length found
29                    max_length = max(max_length, end - start + 1)
30              
31                # Break if the product exceeds the maximum possible product
32                if product > max_possible_product:
33                    break
34
35        return max_length
36
37    # Calculate LCM of two numbers
38    def lcm(self, a: int, b: int) -> int:
39        return a * b // gcd(a, b)
40
41    # Calculate LCM of a list of numbers
42    def lcm_of_list(self, nums: List[int]) -> int:
43        current_lcm = 1
44        for num in nums:
45            current_lcm = self.lcm(current_lcm, num)
46        return current_lcm
47

1class Solution {
2    public int maxLength(int[] nums) {
3        // Initialize maximum mx as 0 and minimum lcm (ml) as 1
4        int mx = 0, ml = 1;
5
6        // Calculate mx (the maximum value in nums) and ml (lcm of all numbers in nums)
7        for (int num : nums) {
8            mx = Math.max(mx, num);
9            ml = lcm(ml, num);
10        }
11
12        // Calculate the product of the maximum number and the lcm
13        int maxProduct = ml * mx;
14        int length = nums.length;
15        int maxSubarrayLength = 0;
16
17        // Iterate through each possible starting point for subarrays
18        for (int i = 0; i < length; ++i) {
19            int product = 1, gcdValue = 0, lcmValue = 1;
20
21            // Consider all subarrays starting with the i-th element
22            for (int j = i; j < length; ++j) {
23                product *= nums[j];
24                gcdValue = gcd(gcdValue, nums[j]);
25                lcmValue = lcm(lcmValue, nums[j]);
26
27                // Check if the condition product == gcd * lcm is satisfied
28                if (product == gcdValue * lcmValue) {
29                    maxSubarrayLength = Math.max(maxSubarrayLength, j - i + 1);
30                }
31
32                // If the product exceeds maxProduct, break out of the loop
33                if (product > maxProduct) {
34                    break;
35                }
36            }
37        }
38
39        // Return the length of the longest subarray found
40        return maxSubarrayLength;
41    }
42
43    // Helper function to compute gcd of two numbers
44    private int gcd(int a, int b) {
45        while (b != 0) {
46            int temp = b;
47            b = a % b;
48            a = temp;
49        }
50        return a;
51    }
52
53    // Helper function to compute lcm of two numbers using the gcd
54    private int lcm(int a, int b) {
55        return a / gcd(a, b) * b;
56    }
57}
58

1#include <vector>
2#include <algorithm>
3#include <numeric>
4using namespace std;
5
6class Solution {
7public:
8    int maxLength(vector<int>& nums) {
9        int maxElement = 0, leastCommonMultiple = 1;
10      
11        // Calculate maximum element and least common multiple of the array
12        for (int x : nums) {
13            maxElement = max(maxElement, x);
14            leastCommonMultiple = lcm(leastCommonMultiple, x);
15        }
16
17        // Calculate the maximum possible product limit
18        long long maxProductLimit = static_cast<long long>(leastCommonMultiple) * maxElement;
19        int n = nums.size();
20        int result = 0;
21
22        // Iterate over each subarray
23        for (int i = 0; i < n; ++i) {
24            long long product = 1, greatestCommonDivisor = 0, currentLCM = 1;
25          
26            // Extend the subarray starting from i
27            for (int j = i; j < n; ++j) {
28                product *= nums[j]; // Calculate product of current subarray
29                greatestCommonDivisor = gcd(greatestCommonDivisor, nums[j]); // Calculate GCD
30                currentLCM = lcm(currentLCM, nums[j]); // Calculate LCM
31
32                // Check if product is equal to GCD times LCM
33                if (product == greatestCommonDivisor * currentLCM) {
34                    result = max(result, j - i + 1); // Update result if condition is met
35                }
36              
37                // Break if product exceeds predefined threshold
38                if (product > maxProductLimit) {
39                    break;
40                }
41            }
42        }
43        return result; // Return the maximum length
44    }
45};
46

1// Function to find the greatest common divisor of two numbers
2function gcd(a: number, b: number): number {
3    while (b !== 0) {
4        let temp = b;
5        b = a % b;
6        a = temp;
7    }
8    return a;
9}
10
11// Function to find the least common multiple of two numbers
12function lcm(a: number, b: number): number {
13    return (a / gcd(a, b)) * b;
14}
15
16// Main function to find the maximum length of a subarray
17function maxLength(nums: number[]): number {
18    let maxElement = 0;
19    let leastCommonMultiple = 1;
20
21    // Calculate the maximum element and least common multiple of the array
22    for (let x of nums) {
23        maxElement = Math.max(maxElement, x);
24        leastCommonMultiple = lcm(leastCommonMultiple, x);
25    }
26
27    // Calculate the maximum possible product limit
28    const maxProductLimit = BigInt(leastCommonMultiple) * BigInt(maxElement);
29    const n = nums.length;
30    let result = 0;
31
32    // Iterate over each subarray
33    for (let i = 0; i < n; ++i) {
34        let product = BigInt(1);
35        let greatestCommonDivisor = 0;
36        let currentLCM = 1;
37
38        // Extend the subarray starting from i
39        for (let j = i; j < n; ++j) {
40            product *= BigInt(nums[j]); // Calculate product of current subarray
41            greatestCommonDivisor = gcd(greatestCommonDivisor, nums[j]); // Calculate GCD
42            currentLCM = lcm(currentLCM, nums[j]); // Calculate LCM
43
44            // Check if product is equal to GCD times LCM
45            if (product === BigInt(greatestCommonDivisor) * BigInt(currentLCM)) {
46                result = Math.max(result, j - i + 1); // Update result if condition is met
47            }
48
49            // Break if product exceeds predefined threshold
50            if (product > maxProductLimit) {
51                break;
52            }
53        }
54    }
55    return result; // Return the maximum length
56}
57

Time and Space Complexity

The given code has a nested loop structure: the outer loop runs n times, and the inner loop can also run up to n times in the worst case. Thus, the time complexity is O(n^2). Inside the inner loop, operations such as gcd and lcm are performed, which are O(log(max_num)), where max_num is the maximum number in the list. This makes the overall time complexity O(n^2 * log(max_num)).

The space complexity of the code is O(1) since only a constant amount of extra space is used, apart from the input list nums.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know