You are given an integer array nums.
The factor score of an array is defined as the product of the LCM and GCD of all elements of that array.
Return the maximum factor score of nums after removing at most one element from it.
Note that both the LCM and GCD of a single number are the number itself, and the factor score of an empty array is 0.
Example 1:
Input: nums = [2,4,8,16]
Output: 64
Explanation:
On removing 2, the GCD of the rest of the elements is 4 while the LCM is 16, which gives a maximum factor score of 4 * 16 = 64.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 60
Explanation:
The maximum factor score of 60 can be obtained without removing any elements.
Example 3:
Input: nums = [3]
Output: 9
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 30Problem Overview: You are given an integer array and must compute the maximum factor score. The factor score of a set of numbers is defined as gcd(nums) * lcm(nums). The task is to evaluate the best possible score when considering the array while optionally excluding one element.
Approach 1: Iterative Approach with Full Array Consideration (O(n² log M) time, O(1) space)
The straightforward strategy is to try every possible scenario where one element is excluded and recompute the GCD and LCM for the remaining elements. For each index i, iterate through the array, skip i, and update the running gcd using Euclid's algorithm while computing lcm = (a * b) / gcd(a, b). This approach repeatedly scans the array, so the cost grows to O(n² log M) due to the repeated GCD calculations. It uses constant extra memory and is easy to implement, which makes it useful for verifying correctness or small input sizes. Concepts rely heavily on math operations and number theory.
Approach 2: Using Prefix and Suffix Arrays (O(n log M) time, O(n) space)
You can avoid recomputing GCD and LCM from scratch by precomputing prefix and suffix values. Build two arrays: prefixGCD/prefixLCM and suffixGCD/suffixLCM. Each prefix entry stores the GCD and LCM from the start of the array up to that index, while suffix arrays store the same information from the end backward. When you remove index i, combine the values from prefix[i-1] and suffix[i+1] to get the GCD and LCM of the remaining elements in constant time. Since each element participates in only a few GCD/LCM calculations, the overall complexity becomes O(n log M). This method leverages properties of arrays and associative math operations.
Recommended for interviews: Start with the iterative approach to demonstrate understanding of how the factor score is computed using GCD and LCM. Interviewers usually expect the optimized prefix–suffix strategy because it removes redundant recomputation and scales linearly with the array size. Showing the transition from O(n²) brute force to O(n log M) optimization demonstrates strong algorithmic reasoning.
This approach involves calculating the LCM and GCD on the full set of numbers as well as for each subset excluding one element. The strategy is to first compute the LCM and GCD of the entire array, and then iteratively recompute these values by removing one element at a time to find the updated factor score.
This solution uses Python's built-in functions to compute the GCD and a custom function to compute the LCM. We iterate over the array, removing each element in turn, and compute the factor score for each subset. The maximum factor score among all subsets is returned.
Time Complexity: O(n^2) since we recompute the LCM and GCD for potentially each subset.
Space Complexity: O(n) due to the new list storing elements after removing one element.
This approach introduces prefix and suffix arrays to store cumulative GCD and LCM computations, optimizing the element removal effect calculation.
This Java solution employs prefix and suffix arrays to store cumulative GCDs. By doing so, the removal of any element's effect can be quickly computed without recalculating GCDs of potentially large subsections of the array, thus optimizing performance over simple iterative recalculation methods.
Java
JavaScript
Time Complexity: O(n) due to the preprocessing of prefix and suffix GCD arrays.
Space Complexity: O(n) for storing these arrays.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Approach with Full Array Consideration | Time Complexity: O(n^2) since we recompute the LCM and GCD for potentially each subset. Space Complexity: O(n) due to the new list storing elements after removing one element. |
| Using Prefix and Suffix Arrays | Time Complexity: O(n) due to the preprocessing of prefix and suffix GCD arrays. Space Complexity: O(n) for storing these arrays. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Full Array Recalculation | O(n² log M) | O(1) | Small arrays or quick brute-force validation |
| Prefix and Suffix GCD/LCM Arrays | O(n log M) | O(n) | General case and interview-ready optimized solution |
Find the Maximum Factor Score of Array | Leetcode weekly-contest-421 | Developer Coder • Developer Coder • 738 views views
Watch 5 more video solutions →Practice Find the Maximum Factor Score of Array with our built-in code editor and test cases.
Practice on FleetCode