Find the Maximum Factor Score of Array solution and explanation
5 more videos on this problem
Find the Maximum Factor Score of Array | Leetcode weekly-contest-421 | Developer CoderDeveloper Coder · 14:04 · 738 views
3334. Find the Maximum Factor Score of Array || Weekly Contest 421 || Leetcode || HindiAshish Kumar · 8:21 · 591 views
Leetcode Weekly Contest 421 | 3334. Find the Maximum Factor Score of Array | CodeFodCodeFod · 7:07 · 556 views
Leetcode Weekly contest 421 | Find the Maximum Factor Score of Array | Solutionak tiwari · 0:18 · 344 views
Q1. Find the Maximum Factor Score of Array || Leetcode Contest Solution Today in c++ ||Jignesh · 0:37 · 195 views
3334. Find the Maximum Factor Score of Array (Leetcode Medium)Programming Live with Larry · 9:57 · 184 views
The problem
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] <= 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.
from math import gcd
from functools import reduce
# Function to calculate LCM
def lcm(a, b):
return a * b // gcd(a, b)
# Function to calculate LCM of an array
def lcm_of_array(arr):
return reduce(lcm, arr, 1)
# Function to calculate GCD of an array
def gcd_of_array(arr):
return reduce(gcd, arr)
# Function to calculate the max factor score
def max_factor_score(nums):
if len(nums) == 1:
return nums[0] ** 2
n = len(nums)
max_score = lcm_of_array(nums) * gcd_of_array(nums)
for i in range(n):
new_nums = nums.copy()
new_nums.pop(i)
current_score = lcm_of_array(new_nums) * gcd_of_array(new_nums)
max_score = max(max_score, current_score)
return max_score
# Example use-case
print(max_factor_score([2, 4, 8, 16])) # Output: 64
print(max_factor_score([1, 2, 3, 4, 5])) # Output: 60#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
long lcm(long a, long b) {
return a * (b / gcd(a, b));
}
long lcm_of_vector(const vector<int>& arr) {
return accumulate(arr.begin(), arr.end(), 1, lcm);
}
long gcd_of_vector(const vector<int>& arr) {
return accumulate(arr.begin(), arr.end(), arr[0], gcd<long, long>);
}
long max_factor_score(vector<int>& nums) {
if (nums.size() == 1) return nums[0] * nums[0];
long max_score = lcm_of_vector(nums) * gcd_of_vector(nums);
for (size_t i = 0; i < nums.size(); ++i) {
vector<int> new_nums = nums;
new_nums.erase(new_nums.begin() + i);
long current_score = lcm_of_vector(new_nums) * gcd_of_vector(new_nums);
max_score = max(max_score, current_score);
}
return max_score;
}
int main() {
vector<int> nums1 = {2, 4, 8, 16};
cout << max_factor_score(nums1) << endl; // Output: 64
vector<int> nums2 = {1, 2, 3, 4, 5};
cout << max_factor_score(nums2) << endl; // Output: 60
return 0;
}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.
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.
import java.util.*;
class Solution {
public int maxFactorScore(int[] nums) {
if (nums.length == 1) return nums[0] * nums[0];
int n = nums.length;
int[] prefixGCD = new int[n];
int[] suffixGCD = new int[n];
prefixGCD[0] = nums[0];
for (int i = 1; i < n; i++) {
prefixGCD[i] = gcd(prefixGCD[i - 1], nums[i]);
}
suffixGCD[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffixGCD[i] = gcd(suffixGCD[i + 1], nums[i]);
}
int overallLCM = lcmOfArray(nums);
int maxScore = overallLCM * prefixGCD[n - 1];
for (int i = 0; i < n; i++) {
int removedGCD = (i == 0 ? suffixGCD[1] : (i == n - 1 ? prefixGCD[n - 2] : gcd(prefixGCD[i - 1], suffixGCD[i + 1])));
maxScore = Math.max(maxScore, overallLCM / nums[i] * removedGCD);
}
return maxScore;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
private int lcmOfArray(int[] arr) {
int ans = 1;
for (int num : arr) {
ans = lcm(ans, num);
}
return ans;
}
private int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
}
public class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxFactorScore(new int[]{2, 4, 8, 16})); // Output: 64
System.out.println(solution.maxFactorScore(new int[]{1, 2, 3, 4, 5})); // Output: 60
}
}function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function lcm(a, b) {
return a * (b / gcd(a, b));
}
function lcmOfArray(arr) {
return arr.reduce((acc, num) => lcm(acc, num), 1);
}
function maxFactorScore(nums) {
if (nums.length === 1) return nums[0] * nums[0];
const n = nums.length;
const prefixGCD = Array(n).fill(0);
const suffixGCD = Array(n).fill(0);
prefixGCD[0] = nums[0];
for (let i = 1; i < n; i++) {
prefixGCD[i] = gcd(prefixGCD[i - 1], nums[i]);
}
suffixGCD[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
suffixGCD[i] = gcd(suffixGCD[i + 1], nums[i]);
}
const overallLCM = lcmOfArray(nums);
let maxScore = overallLCM * prefixGCD[n - 1];
for (let i = 0; i < n; i++) {
const removedGCD = i === 0 ? suffixGCD[1] : (i === n - 1 ? prefixGCD[n - 2] : gcd(prefixGCD[i - 1], suffixGCD[i + 1]));
maxScore = Math.max(maxScore, overallLCM / nums[i] * removedGCD);
}
return maxScore;
}
console.log(maxFactorScore([2, 4, 8, 16])); // Output: 64
console.log(maxFactorScore([1, 2, 3, 4, 5])); // Output: 60;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.
Time Complexity: O(n) due to the preprocessing of prefix and suffix GCD arrays.
Space Complexity: O(n) for storing these arrays.
Approach 3: Default Approach
function maxScore(nums: number[]): number {
const n = nums.length;
const sufGcd: number[] = Array(n + 1).fill(0);
const sufLcm: number[] = Array(n + 1).fill(1);
for (let i = n - 1; i >= 0; i--) {
sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
}
let ans = sufGcd[0] * sufLcm[0];
let preGcd = 0,
preLcm = 1;
for (let i = 0; i < n; i++) {
ans = Math.max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
preGcd = gcd(preGcd, nums[i]);
preLcm = lcm(preLcm, nums[i]);
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
function lcm(a: number, b: number): number {
return (a / gcd(a, b)) * b;
}func maxScore(nums []int) int64 {
n := len(nums)
sufGcd := make([]int64, n+1)
sufLcm := make([]int64, n+1)
sufLcm[n] = 1
for i := n - 1; i >= 0; i-- {
sufGcd[i] = gcd(sufGcd[i+1], int64(nums[i]))
sufLcm[i] = lcm(sufLcm[i+1], int64(nums[i]))
}
ans := sufGcd[0] * sufLcm[0]
preGcd, preLcm := int64(0), int64(1)
for i := 0; i < n; i++ {
ans = max(ans, gcd(preGcd, sufGcd[i+1])*lcm(preLcm, sufLcm[i+1]))
preGcd = gcd(preGcd, int64(nums[i]))
preLcm = lcm(preLcm, int64(nums[i]))
}
return ans
}
func gcd(a, b int64) int64 {
if b == 0 {
return a
}
return gcd(b, a%b)
}
func lcm(a, b int64) int64 {
return a / gcd(a, b) * b
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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).