We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Factor Score of Array

Number: 3593

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, the factor score is defined as the product of the LCM and GCD of all its elements. You may remove at most one element from the array. Return the maximum factor score obtainable. Note that for a single number, both its LCM and GCD are the number itself, and the factor score of an empty array is 0.

Key Insights

  • Removing one element might improve the overall factor score by altering the GCD and LCM values.
  • The problem requires evaluating the score for the entire array and for each possibility created by removing one element.
  • Since nums.length ≤ 100, a brute-force check of all removal possibilities is efficient.
  • Use helper functions to compute the GCD and LCM over an array.
  • Remember the mathematical relation: lcm(a, b) = (a * b) / gcd(a, b).

Space and Time Complexity

Time Complexity: O(n^2) in the worst case (n removals and each removal computes GCD/LCM in O(n), and n ≤ 100).
Space Complexity: O(n) for storing subarrays when checking removals.

Solution

We approach the problem by first computing the factor score (GCD * LCM) of the original array without any removals. Then, for each element, we remove that element and recalculate the factor score on the remaining elements. We keep track of the maximum score encountered.
Data Structures: We primarily use arrays (or lists) and helper functions for GCD and LCM.
Algorithm:

  1. Create helper functions to compute the GCD and LCM for an array.
  2. Calculate the factor score (GCD multiplied by LCM) for the full array.
  3. Iterate over the array, remove each element in turn, compute the new factor score, and update the maximum score.
  4. Return the maximum score.

Code Solutions

import math

# Function to compute the factor score of an array
def maxFactorScore(nums):
    n = len(nums)
    
    # Helper function to compute GCD for a list of numbers
    def compute_gcd(arr):
        result = arr[0]
        for num in arr[1:]:
            result = math.gcd(result, num)
        return result
    
    # Helper function to compute LCM for a list of numbers
    def compute_lcm(arr):
        def lcm(a, b):
            return a * b // math.gcd(a, b)
        result = arr[0]
        for num in arr[1:]:
            result = lcm(result, num)
        return result
    
    # Function to compute the factor score (GCD * LCM)
    def factor_score(arr):
        if not arr:
            return 0
        return compute_gcd(arr) * compute_lcm(arr)
    
    # Start with the score of the original array (no removal)
    max_score = factor_score(nums)
    
    # Try removing each element one by one and update the maximum score
    for i in range(n):
        new_nums = nums[:i] + nums[i+1:]
        max_score = max(max_score, factor_score(new_nums))
    
    return max_score

# Example usage:
print(maxFactorScore([2,4,8,16]))  # expected output: 64
print(maxFactorScore([1,2,3,4,5])) # expected output: 60
print(maxFactorScore([3]))         # expected output: 9
← Back to All Questions