Watch 6 video solutions for Find the Maximum Factor Score of Array, a medium level problem involving Array, Math, Number Theory. This walkthrough by Developer Coder has 738 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |