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).

Description Hints 2 Solution Video 14:04

3334. Find the Maximum Factor Score of Array

Medium41.0% acceptance1 company

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

Asked at 1 company

Info Edge

Topics

Hints open one at a time

Hint 1

Use brute force approach with two loops.

Hint 2

Optimize using prefix and suffix arrays.

14:04

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution