Find the Maximum Factor Score of Array - Practice Coding Problems

Find the Maximum Factor Score of Array - Problem

You are given an integer array nums. The factor score of an array is defined as the product of the LCM (Least Common Multiple) and GCD (Greatest Common Divisor) of all elements of that array.

Return the maximum factor score of nums after removing at most one element from it.

Note:

Both the LCM and GCD of a single number are the number itself
The factor score of an empty array is 0

Input & Output

Example 1 — Powers of 2

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

› Output: 64

💡 Note: Removing the first element (2) gives us [4,8,16]. GCD(4,8,16) = 4, LCM(4,8,16) = 16, so factor score = 4 × 16 = 64. This is the maximum possible.

Example 2 — Small Array

$ Input: nums = [1,2]

› Output: 4

💡 Note: Original array: GCD(1,2) = 1, LCM(1,2) = 2, score = 2. Remove 1: [2] gives score = 2×2 = 4. Remove 2: [1] gives score = 1×1 = 1. Maximum is 4.

Example 3 — Single Element

$ Input: nums = [3]

› Output: 9

💡 Note: Single element: GCD(3) = 3, LCM(3) = 3, factor score = 3 × 3 = 9. Removing the element gives an empty array with score 0. Maximum is 9.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [2,4,8,16] with factor score = GCD×LCM

Try Removals

Test removing each element and calculate new factor scores

Maximum Found

Return the highest factor score: 64

Key Takeaway

🎯 Key Insight: Removing an element that reduces the GCD more than it reduces the LCM can increase the overall factor score

Asked in

G Google 35 f Meta 28 ⊞ Microsoft 22 a Amazon 18

The key insight is that the factor score (GCD × LCM) can be maximized by strategically removing one element. The optimized approach uses prefix/suffix arrays to avoid redundant GCD/LCM calculations. Time: O(n log max), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Prefix/Suffix Arrays	O(n × log(max(nums)))	O(n)	Pre-compute prefix and suffix GCD/LCM to avoid recalculating for each removal
Brute Force - Try All Removals	O(n² × log(max(nums)))	O(1)	Calculate factor score for original array and after removing each element

Optimized with Prefix/Suffix Arrays — Algorithm Steps

Step 1: Pre-compute prefix GCD/LCM arrays (left to right)
Step 2: Pre-compute suffix GCD/LCM arrays (right to left)
Step 3: For each removal, combine prefix[i-1] with suffix[i+1]
Step 4: Return maximum factor score found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix

Pre-compute GCD/LCM from left to each position

Build Suffix

Pre-compute GCD/LCM from right to each position

Combine

For each removal, combine prefix[i-1] with suffix[i+1]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

long long max(long long a, long long b) {
    return a > b ? a : b;
}

long long solution(int* nums, int size) {
    if (size == 0) return 0;
    if (size == 1) return (long long)nums[0] * nums[0];
    
    long long prefixGcd[1000], prefixLcm[1000];
    long long suffixGcd[1000], suffixLcm[1000];
    
    prefixGcd[0] = nums[0];
    prefixLcm[0] = nums[0];
    
    for (int i = 1; i < size; i++) {
        prefixGcd[i] = gcd(prefixGcd[i-1], nums[i]);
        prefixLcm[i] = lcm(prefixLcm[i-1], nums[i]);
    }
    
    suffixGcd[size-1] = nums[size-1];
    suffixLcm[size-1] = nums[size-1];
    
    for (int i = size-2; i >= 0; i--) {
        suffixGcd[i] = gcd(suffixGcd[i+1], nums[i]);
        suffixLcm[i] = lcm(suffixLcm[i+1], nums[i]);
    }
    
    long long maxScore = 0;
    maxScore = max(maxScore, prefixGcd[size-1] * prefixLcm[size-1]);
    
    for (int i = 0; i < size; i++) {
        if (i == 0) {
            if (size > 1) {
                long long g = suffixGcd[1];
                long long l = suffixLcm[1];
                maxScore = max(maxScore, g * l);
            }
        } else if (i == size-1) {
            long long g = prefixGcd[size-2];
            long long l = prefixLcm[size-2];
            maxScore = max(maxScore, g * l);
        } else {
            long long g = gcd(prefixGcd[i-1], suffixGcd[i+1]);
            long long l = lcm(prefixLcm[i-1], suffixLcm[i+1]);
            maxScore = max(maxScore, g * l);
        }
    }
    
    return maxScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int size = 0;
    
    char* ptr = line + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max(nums)))

Single pass to build prefix/suffix arrays, then one pass to check each removal

⚡ Linearithmic

Space Complexity

O(n)

Store prefix and suffix GCD/LCM arrays of size n

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Prefix/Suffix Arrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler