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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Factor Score of Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The factor score is calculated as GCD(nums) * LCM(nums).
  • Removing an element can potentially change the GCD and LCM.
  • We need to consider both cases: removing one element and not removing any.
  • GCD can be computed using the gcd function and LCM can be derived from the relationship: LCM(a, b) = (a * b) / GCD(a, b).
  • The constraints (1 <= nums[i] <= 30) allow for a manageable computation of GCD and LCM.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve this problem, we can follow these steps:

  1. Calculate the GCD of the entire array.
  2. Calculate the LCM of the entire array.
  3. Iterate through the array and for each element, calculate the GCD and LCM of the remaining elements (after removing the current element).
  4. Compute the factor score for both the original array and the modified arrays (after removals).
  5. Keep track of the maximum factor score found.

Data Structures Used

  • Arrays for storing numbers.
  • Integer variables to store GCD and LCM values.

Code Solutions

import math
from functools import reduce
from math import gcd

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

def findMaxFactorScore(nums):
    def compute_gcd(arr):
        return reduce(gcd, arr)

    def compute_lcm(arr):
        return reduce(lcm, arr)

    n = len(nums)
    max_score = 0

    # Calculate GCD and LCM of the entire array
    total_gcd = compute_gcd(nums)
    total_lcm = compute_lcm(nums)
    max_score = max(max_score, total_gcd * total_lcm)

    for i in range(n):
        # Create a new array without the i-th element
        new_nums = nums[:i] + nums[i+1:]
        if new_nums:
            new_gcd = compute_gcd(new_nums)
            new_lcm = compute_lcm(new_nums)
            max_score = max(max_score, new_gcd * new_lcm)

    return max_score
← Back to All Questions