LeetCode 3334 - Find the Maximum Factor Score of Array

The problem asks us to compute the maximum factor score of an array of integers, where the factor score is defined as the product of the GCD (greatest common divisor) and LCM (least common multiple) of all elements in the array.

leetcodemediumarraymathnumber-theory

LeetCode Problem 3334

Difficulty: 🟡 Medium
Topics: Array, Math, Number Theory

Solution

Problem Understanding

The problem asks us to compute the maximum factor score of an array of integers, where the factor score is defined as the product of the GCD (greatest common divisor) and LCM (least common multiple) of all elements in the array. We are allowed to remove at most one element to maximize this score.

The input is an array nums of length n where 1 <= n <= 100, and each element satisfies 1 <= nums[i] <= 30. The output is a single integer representing the maximum factor score achievable.

Key constraints and implications:

  1. The array is small (n <= 100), so solutions with nested loops are feasible.
  2. Numbers are small (nums[i] <= 30), so operations like computing LCM or GCD are fast.
  3. Factor score for a single element is simply the square of that number.
  4. Factor score for an empty array is 0, which is an important edge case when n = 1.
  5. Removing an element is optional; sometimes the maximum factor score occurs without removing any elements.

Edge cases to consider:

  • Single-element array: removing the element yields an empty array with score 0.
  • Arrays with identical elements: removing one element might not change the GCD or LCM.
  • Arrays with co-prime elements: the GCD could be 1, so removing certain elements might improve the score.

Approaches

Brute Force

The brute-force approach is to consider removing each element one by one (including the option of removing none). For each possible array:

  1. Compute the GCD of all remaining elements.
  2. Compute the LCM of all remaining elements.
  3. Compute the product of GCD and LCM, and track the maximum value.

This approach is guaranteed to be correct because it evaluates all possible arrays formed by removing at most one element. However, computing GCD and LCM repeatedly for subarrays makes it somewhat redundant and could be optimized.

Optimal Approach

Key observations for optimization:

  1. GCD and LCM are associative, meaning GCD(a, b, c) = GCD(GCD(a, b), c) and similarly for LCM.
  2. We can precompute prefix and suffix arrays for GCD and LCM. This allows calculating the GCD and LCM of the array excluding any one element in O(1) time.

The steps are:

  1. Compute prefix GCD and LCM arrays from left to right.
  2. Compute suffix GCD and LCM arrays from right to left.
  3. For each element, calculate the GCD and LCM of the remaining array using prefix and suffix values.
  4. Compute the factor score for each option and track the maximum.

This reduces repeated computations and is efficient for n <= 100.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compute GCD and LCM for all subarrays
Optimal O(n) O(n) Use prefix and suffix arrays for constant-time GCD and LCM calculation after preprocessing

Algorithm Walkthrough

  1. Initialize arrays prefixGCD, prefixLCM, suffixGCD, and suffixLCM of length n.
  2. Fill prefixGCD and prefixLCM from left to right: each index stores the GCD/LCM of elements from the start up to that index.
  3. Fill suffixGCD and suffixLCM from right to left: each index stores the GCD/LCM from that index to the end.
  4. Initialize a variable maxScore with the factor score of the full array (without removing any element).
  5. Iterate over each index i in nums to simulate removing nums[i]:

  • Compute the GCD and LCM of the remaining array using prefix and suffix arrays:

  • GCD = GCD(prefixGCD[i-1], suffixGCD[i+1]) (handle edges)

  • LCM = LCM(prefixLCM[i-1], suffixLCM[i+1]) (handle edges)

  • Compute factor score and update maxScore if it is higher.

  1. Return maxScore.

Why it works: The algorithm correctly computes the factor score for the full array and for each array formed by removing exactly one element. Prefix and suffix arrays ensure that GCD and LCM can be computed in constant time for each removal, maintaining correctness due to the associative property of GCD and LCM.

Python Solution

from math import gcd
from functools import reduce
from typing import List

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        
        prefixGCD = [0] * n
        prefixLCM = [0] * n
        suffixGCD = [0] * n
        suffixLCM = [0] * n
        
        prefixGCD[0] = nums[0]
        prefixLCM[0] = nums[0]
        for i in range(1, n):
            prefixGCD[i] = gcd(prefixGCD[i-1], nums[i])
            prefixLCM[i] = lcm(prefixLCM[i-1], nums[i])
        
        suffixGCD[-1] = nums[-1]
        suffixLCM[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suffixGCD[i] = gcd(suffixGCD[i+1], nums[i])
            suffixLCM[i] = lcm(suffixLCM[i+1], nums[i])
        
        maxScore = prefixGCD[-1] * prefixLCM[-1]
        
        for i in range(n):
            leftGCD = prefixGCD[i-1] if i > 0 else 0
            rightGCD = suffixGCD[i+1] if i < n-1 else 0
            combinedGCD = gcd(leftGCD, rightGCD) if leftGCD and rightGCD else leftGCD or rightGCD
            
            leftLCM = prefixLCM[i-1] if i > 0 else 1
            rightLCM = suffixLCM[i+1] if i < n-1 else 1
            combinedLCM = leftLCM
            if i < n-1:
                combinedLCM = lcm(leftLCM, rightLCM)
            
            maxScore = max(maxScore, combinedGCD * combinedLCM)
        
        return maxScore

Explanation: The Python code follows the algorithm closely. prefixGCD and suffixGCD store the cumulative GCDs, prefixLCM and suffixLCM store cumulative LCMs. For each potential removal, we compute the GCD and LCM of the remaining elements using these arrays, and update maxScore.

Go Solution

package main

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func lcm(a, b int) int {
    return a * b / gcd(a, b)
}

func maxScore(nums []int) int64 {
    n := len(nums)
    if n == 0 {
        return 0
    }
    
    prefixGCD := make([]int, n)
    prefixLCM := make([]int, n)
    suffixGCD := make([]int, n)
    suffixLCM := make([]int, n)
    
    prefixGCD[0] = nums[0]
    prefixLCM[0] = nums[0]
    for i := 1; i < n; i++ {
        prefixGCD[i] = gcd(prefixGCD[i-1], nums[i])
        prefixLCM[i] = lcm(prefixLCM[i-1], nums[i])
    }
    
    suffixGCD[n-1] = nums[n-1]
    suffixLCM[n-1] = nums[n-1]
    for i := n-2; i >= 0; i-- {
        suffixGCD[i] = gcd(suffixGCD[i+1], nums[i])
        suffixLCM[i] = lcm(suffixLCM[i+1], nums[i])
    }
    
    maxScore := int64(prefixGCD[n-1] * prefixLCM[n-1])
    
    for i := 0; i < n; i++ {
        leftGCD := 0
        if i > 0 {
            leftGCD = prefixGCD[i-1]
        }
        rightGCD := 0
        if i < n-1 {
            rightGCD = suffixGCD[i+1]
        }
        combinedGCD := leftGCD
        if leftGCD != 0 && rightGCD != 0 {
            combinedGCD = gcd(leftGCD, rightGCD)
        } else if rightGCD != 0 {
            combinedGCD = rightGCD
        }
        
        leftLCM := 1
        if i > 0 {
            leftLCM = prefixLCM[i-1]
        }
        rightLCM := 1
        if i