Problem Description

You are given an integer array nums.

The factor score of an array is calculated as the product of two values:

• The LCM (Least Common Multiple) of all elements in the array
• The GCD (Greatest Common Divisor) of all elements in the array

Your task is to find the maximum possible factor score after removing at most one element from the array. This means you can either:

1. Keep all elements (remove nothing)
2. Remove exactly one element

Important notes:

• For a single-element array, both LCM and GCD equal the element itself
• For an empty array, the factor score is 0
• The factor score = LCM(array) × GCD(array)

For example, if nums = [6, 12, 18]:

• Without removing any element: GCD(6,12,18) = 6, LCM(6,12,18) = 36, factor score = 6 × 36 = 216
• After removing 6: GCD(12,18) = 6, LCM(12,18) = 36, factor score = 6 × 36 = 216
• After removing 12: GCD(6,18) = 6, LCM(6,18) = 18, factor score = 6 × 18 = 108
• After removing 18: GCD(6,12) = 6, LCM(6,12) = 12, factor score = 6 × 12 = 72

The maximum factor score would be 216.

Intuition

To find the maximum factor score, we need to consider all possible scenarios: keeping all elements or removing exactly one element. The brute force approach would be to try removing each element one by one and calculate the factor score for each case, but this would involve recalculating GCD and LCM from scratch each time, which is inefficient.

The key insight is that when we remove element at index i, the resulting array is essentially the combination of two parts:

• Elements before index i (prefix: nums[0...i-1])
• Elements after index i (suffix: nums[i+1...n-1])

The GCD and LCM of the resulting array would be:

• GCD = gcd(GCD_of_prefix, GCD_of_suffix)
• LCM = lcm(LCM_of_prefix, LCM_of_suffix)

This observation leads us to a preprocessing strategy. If we precompute the GCD and LCM values for all suffixes, we can efficiently calculate the factor score when any element is removed.

As we iterate through the array from left to right:

• We maintain running prefix GCD and LCM values
• For each position i, we can instantly know what the GCD and LCM would be if we removed element i by combining:
  • The prefix values (elements before i)
  • The precomputed suffix values (elements after i)

This way, we only need one pass to precompute suffix values and another pass to check all possibilities, reducing the time complexity significantly. The solution also handles the case where we don't remove any element (which is just the GCD and LCM of the entire array).

Learn more about Math patterns.

Solution Approach

The implementation uses prefix and suffix arrays to efficiently calculate the factor score for all possible scenarios.

Step 1: Initialize Suffix Arrays

We create two arrays to store suffix GCD and LCM values:

• suf_gcd[i] stores the GCD of all elements from index i to the end
• suf_lcm[i] stores the LCM of all elements from index i to the end

suf_gcd = [0] * (n + 1)  # Extra element for boundary condition
suf_lcm = [0] * n + [1]  # Initialize last element as 1 for LCM

Step 2: Build Suffix Arrays (Right to Left)

We iterate from the last element to the first, building up the suffix values:

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

For each position i, we combine the current element nums[i] with the suffix starting at i+1.

Step 3: Calculate Initial Answer (No Removal)

First, we consider keeping all elements:

ans = suf_gcd[0] * suf_lcm[0]

This gives us the factor score of the entire array.

Step 4: Check All Removal Scenarios

We maintain prefix GCD and LCM as we iterate through the array:

pre_gcd, pre_lcm = 0, 1  # Identity values for GCD and LCM
for i, x in enumerate(nums):
    # Calculate score if we remove element at index i
    ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]))
  
    # Update prefix values for next iteration
    pre_gcd = gcd(pre_gcd, x)
    pre_lcm = lcm(pre_lcm, x)

When removing element at index i:

• The remaining array's GCD = gcd(prefix_gcd, suffix_gcd)
• The remaining array's LCM = lcm(prefix_lcm, suffix_lcm)
• Factor score = GCD × LCM

Key Implementation Details:

1. Identity Values: We use 0 for GCD and 1 for LCM as identity values. This ensures gcd(0, x) = x and lcm(1, x) = x.

2. Boundary Handling: The suffix arrays have an extra element to handle the case when we're at the last position (empty suffix).

3. Maximum Tracking: We continuously update ans with the maximum factor score found.

The algorithm runs in O(n × log(max_value)) time, where the logarithmic factor comes from the GCD/LCM calculations, and uses O(n) extra space for the suffix arrays.

Example Walkthrough

Let's walk through the solution with nums = [4, 6, 12].

Step 1: Build Suffix Arrays

We initialize suffix arrays with extra space:

• suf_gcd = [0, 0, 0, 0] (4 elements)
• suf_lcm = [0, 0, 0, 1] (last element is 1)

Building from right to left:

• i = 2: suf_gcd[2] = gcd(0, 12) = 12, suf_lcm[2] = lcm(1, 12) = 12
• i = 1: suf_gcd[1] = gcd(12, 6) = 6, suf_lcm[1] = lcm(12, 6) = 12
• i = 0: suf_gcd[0] = gcd(6, 4) = 2, suf_lcm[0] = lcm(12, 4) = 12

Final suffix arrays:

• suf_gcd = [2, 6, 12, 0]
• suf_lcm = [12, 12, 12, 1]

Step 2: Calculate Initial Answer (Keep All Elements)

Factor score with all elements = suf_gcd[0] × suf_lcm[0] = 2 × 12 = 24

Step 3: Check Each Removal Scenario

Initialize prefix values: pre_gcd = 0, pre_lcm = 1

Iteration 1 (i = 0, removing 4):

• Remaining elements: [6, 12]
• GCD = gcd(pre_gcd=0, suf_gcd[1]=6) = 6
• LCM = lcm(pre_lcm=1, suf_lcm[1]=12) = 12
• Factor score = 6 × 12 = 72
• Update: ans = max(24, 72) = 72
• Update prefix: pre_gcd = gcd(0, 4) = 4, pre_lcm = lcm(1, 4) = 4

Iteration 2 (i = 1, removing 6):

• Remaining elements: [4, 12]
• GCD = gcd(pre_gcd=4, suf_gcd[2]=12) = 4
• LCM = lcm(pre_lcm=4, suf_lcm[2]=12) = 12
• Factor score = 4 × 12 = 48
• Update: ans = max(72, 48) = 72
• Update prefix: pre_gcd = gcd(4, 6) = 2, pre_lcm = lcm(4, 6) = 12

Iteration 3 (i = 2, removing 12):

• Remaining elements: [4, 6]
• GCD = gcd(pre_gcd=2, suf_gcd[3]=0) = 2
• LCM = lcm(pre_lcm=12, suf_lcm[3]=1) = 12
• Factor score = 2 × 12 = 24
• Update: ans = max(72, 24) = 72

Final Answer: 72 (achieved by removing element 4)

The solution efficiently considers all scenarios:

• Keep all: factor score = 24
• Remove 4: factor score = 72 ✓ (maximum)
• Remove 6: factor score = 48
• Remove 12: factor score = 24

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log(max(nums)))

The algorithm consists of three main parts:

1. Preprocessing suffix arrays (O(n * log(max(nums)))):

   • The loop runs n times
   • Each iteration computes gcd(suf_gcd[i + 1], nums[i]) and lcm(suf_lcm[i + 1], nums[i])
   • Both GCD and LCM operations have time complexity O(log(max(nums))) using Euclidean algorithm
   • Total: O(n * log(max(nums)))

2. Main loop to find maximum score (O(n * log(max(nums)))):

   • The loop runs n times
   • Each iteration computes:
     • gcd(pre_gcd, suf_gcd[i + 1]) - O(log(max(nums)))
     • lcm(pre_lcm, suf_lcm[i + 1]) - O(log(max(nums)))
     • gcd(pre_gcd, x) - O(log(max(nums)))
     • lcm(pre_lcm, x) - O(log(max(nums)))
   • Total: O(n * log(max(nums)))

Overall time complexity: O(n * log(max(nums)))

Space Complexity: O(n)

The algorithm uses:

• suf_gcd array of size n + 1: O(n)
• suf_lcm array of size n + 1: O(n)
• pre_gcd and pre_lcm variables: O(1)
• Other variables (ans, i, x): O(1)

Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in LCM Calculation

The most critical pitfall in this solution is potential integer overflow when calculating the LCM. The LCM of two numbers can grow very quickly, and multiplying it with the GCD can easily exceed integer limits.

Problem Example:

# Consider nums = [1000000, 999999, 999998]
# LCM can become extremely large, causing overflow
# Even with Python's arbitrary precision, the multiplication a * b in lcm() 
# could be problematic in other languages

Solution:

• In Python, this is less of an issue due to arbitrary precision integers, but be mindful of performance
• For other languages, consider using long long or BigInteger types
• Add overflow checking if needed:

def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    g = gcd(a, b)
    # Check for potential overflow before multiplication
    result = (a // g) * b  # Divide first to reduce overflow risk
    return result

2. Incorrect Identity Values for GCD

Using the wrong identity value for GCD operations can lead to incorrect results.

Problem:

# Wrong: Using 1 as identity for GCD
prefix_gcd = 1  # This would make gcd(1, x) = 1 for any x

# Correct: Using 0 as identity for GCD
prefix_gcd = 0  # This makes gcd(0, x) = x

Solution: Always use 0 as the identity for GCD operations, as gcd(0, x) = x for any positive integer x.

3. Edge Case: Single Element Array

When the array has only one element, removing it would leave an empty array, which should return 0.

Problem:

# If nums = [5], removing the only element should give score = 0
# But suffix_gcd[1] and suffix_lcm[1] might not handle this correctly

Solution: The current implementation handles this correctly by initializing:

• suffix_gcd[n] = 0 (GCD of empty set)
• suffix_lcm[n] = 1 (LCM of empty set)
• When both are combined: gcd(0, 0) * lcm(1, 1) = 0 * 1 = 0

4. LCM of Zero Values

If the array contains zeros, special handling is needed.

Problem:

# If nums contains 0, lcm(0, x) should be 0
# But the formula a * b // gcd(a, b) could cause division issues

Solution: The current implementation correctly handles this with the guard clause:

if a == 0 or b == 0:
    return 0

5. Not Considering the "No Removal" Case

A common mistake is forgetting to include the original array's score (without removing any element).

Problem:

# Wrong: Only considering cases where we remove an element
max_score = 0
for i in range(n):
    # Only calculating scores with removal
    ...

# Correct: Initialize with the full array's score
max_score = suffix_gcd[0] * suffix_lcm[0]

Solution: Always initialize the answer with the factor score of the complete array before checking removal scenarios.