#3334

Medium

LeetCode Problem Workspace

Find the Maximum Factor Score of Array

Calculate the maximum factor score of an integer array by optionally removing one element using LCM and GCD computations.

array math number theory

Problem Statement

You are given an integer array nums. The factor score of an array is defined as the product of the least common multiple (LCM) and the greatest common divisor (GCD) of all elements. You may remove at most one element from nums to maximize this score.

Return the maximum factor score obtainable. Consider all possible single-element removals or keeping the array intact, and compute the resulting LCM and GCD combinations to find the largest product.

Examples

Example 1

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

Output: 64

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

The maximum factor score of 60 can be obtained without removing any elements.

Example 3

Input: nums = [3]

Output: 9

Example details omitted.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 30

Solution Approach

Brute Force Removal and Compute

Iterate over each element, temporarily remove it, compute the GCD and LCM of the remaining array, and calculate the factor score. Keep track of the maximum score found. This aligns with the array plus math pattern and leverages number theory properties.

Handle Full Array Without Removal

Calculate the factor score for the original array without removing any element. Some arrays may already have the maximum score, so this ensures you do not miss the optimal case. This step addresses a common failure mode of skipping the no-removal scenario.

Optimize LCM and GCD Computation

Use iterative pairwise computation for LCM and GCD to avoid redundant calculations. Precompute prefix and suffix GCDs and LCMs if needed for efficiency. This prevents performance issues when naively recomputing for each removal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on computing LCM and GCD for each removal, roughly O(n^2) with naive methods. Space complexity is O(n) if prefix and suffix arrays are used for optimization.

What Interviewers Usually Probe

Are you accounting for the no-removal case explicitly?
How are you computing LCM efficiently for multiple elements?
What happens when the array has a single element?

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider the original array without removing any element.
Miscomputing LCM or GCD for more than two numbers.
Ignoring small arrays where removing an element is not possible or unnecessary.

Follow-up variants

Maximize sum of LCM and GCD instead of product.
Allow removing up to two elements to maximize factor score.
Apply the same problem on a multi-dimensional array.

FAQ

What is the maximum factor score in 'Find the Maximum Factor Score of Array'?

It is the largest product of LCM and GCD after optionally removing one element from the array.

Can I remove more than one element to increase the factor score?

No, the problem allows removing at most one element to maximize the score.

How do I compute LCM and GCD efficiently for multiple numbers?

Use iterative pairwise LCM and GCD computation and consider prefix/suffix precomputations to reduce redundant calculations.

What should I do if the array has only one element?

Compute the factor score as the element squared since removing it is optional but would leave an empty array.

Does removing an element always increase the factor score?

Not necessarily; sometimes the original array without removal gives the maximum factor score.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        suf_gcd = [0] * (n + 1)
        suf_lcm = [0] * n + [1]
        for i in range(n - 1, -1, -1):
            suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
            suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i])
        ans = suf_gcd[0] * suf_lcm[0]
        pre_gcd, pre_lcm = 0, 1
        for i, x in enumerate(nums):
            ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]))
            pre_gcd = gcd(pre_gcd, x)
            pre_lcm = lcm(pre_lcm, x)
        return ans

Continue Practicing

#3336 find the number of subsequences with equal gcd #3326 minimum division operations to make array non decreasing #3312 sorted gcd pair queries