Skip to main content
Talentd

Find the Maximum Factor Score of Array - Solution & Explanation

MediumArrayMathNumber Theory10 min readAsked at: Info Edge
Practice this problem

Problem Statement

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 <= 100
  • 1 <= nums[i] <= 30

Approach Overview

Problem 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 1: Iterative Approach with Full Array Consideration

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Using Prefix and Suffix Arrays

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n) due to the preprocessing of prefix and suffix GCD arrays.

Space Complexity: O(n) for storing these arrays.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Full Array RecalculationO(n² log M)O(1)Small arrays or quick brute-force validation
Prefix and Suffix GCD/LCM ArraysO(n log M)O(n)General case and interview-ready optimized solution

Video Solution

Find the Maximum Factor Score of Array | Leetcode weekly-contest-421 | Developer Coder • Developer Coder • 738 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find the Maximum Factor Score of Array easy or hard?
The problem is rated Medium because the individual operations—GCD and LCM—are simple, but combining them efficiently requires recognizing the prefix–suffix optimization. Many candidates first implement the O(n²) brute force before improving it to the linear-pass approach.
Find the Maximum Factor Score of Array Python/Java solution
Python solutions typically use the built-in math.gcd function and compute LCM using (a * b) // gcd(a, b). Java implementations use iterative GCD functions with long arithmetic to avoid overflow. Both versions implement the prefix–suffix optimization to achieve O(n log M) complexity.
How to solve Find the Maximum Factor Score of Array in O(n)?
Strict O(n) is difficult because computing GCD and LCM involves logarithmic operations. The practical optimal solution runs in O(n log M) by precomputing prefix and suffix GCD and LCM arrays. Each index removal is evaluated in constant time using those precomputed values.
What is the best approach for Find the Maximum Factor Score of Array?
The most efficient solution uses prefix and suffix arrays to store running GCD and LCM values. When removing an element, combine the prefix and suffix results to compute the new GCD and LCM in constant time. This reduces the complexity to O(n log M), which is significantly faster than recomputing values for every index.
Is Find the Maximum Factor Score of Array asked at Google/Amazon/Meta?
Problems involving GCD, LCM, and prefix–suffix optimizations commonly appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the same techniques—number theory with prefix computation—are frequently tested in algorithm rounds.
What data structure is used in Find the Maximum Factor Score of Array?
The main structure used is prefix and suffix arrays that store cumulative GCD and LCM values. These arrays allow fast recomputation when an element is excluded. The algorithm also relies on number theory utilities such as the Euclidean algorithm for GCD.
What is the time complexity of Find the Maximum Factor Score of Array?
The optimized solution runs in O(n log M), where n is the array length and M is the maximum value in the array. The log M factor comes from repeated GCD calculations using Euclid’s algorithm. The brute-force approach that recomputes GCD and LCM for every removal takes O(n² log M).

Ready to solve this problem?

Practice Find the Maximum Factor Score of Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Greatest Common Divisor of Strings

Next

Remove One Element to Make the Array Strictly Increasing