3334. Find the Maximum Factor Score of Array

MediumArrayMathNumber Theory

Problem Description

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 in that array.

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

Note: The LCM and GCD of a single number are the number itself, and the factor score of an empty array is 0.

Intuition

The problem requires us to find the maximum factor score by potentially removing one element from the array. The factor score is derived from the product of the LCM and GCD of the array's elements. Removing an element should only increase this product if it leads to a combination of values with a better balance between their LCM and GCD.

To solve this, we pre-compute the GCD and LCM of segments of the array, allowing us to consider removing each element efficiently:

Compute suffix GCD and LCM for easy access to the GCD and LCM of elements after a given index.
Calculate the prefix GCD and LCM while iterating through the array, giving the GCD and LCM of elements before a given index.
For each element in the array, consider its removal by using the prefix and suffix pre-computed values to evaluate the potential factor score.
Track the maximum factor score encountered through this iteration process, which yields the desired result.

The technique focuses on balancing the computational costs by leveraging the properties of GCD and LCM while considering the impact of removing each element in the array.

Learn more about Math patterns.

Solution Approach

The solution is structured to efficiently calculate the maximum factor score through careful management of prefix and suffix computations. Here's the breakdown of the approach:

Initialize Arrays:
- suf_gcd and suf_lcm arrays are initialized to store the suffix GCD and LCM values. The suffix in this context refers to the segment of the array starting from a given index to the end.
- suf_gcd is initially filled with zeros, while suf_lcm is filled with ones for a base case analysis.
Compute Suffix GCD and LCM:
- Iterate over the array in reverse to populate suf_gcd and suf_lcm.
- For each element nums[i], compute:
  - suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
  - suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i])
- This gives the GCD and LCM of the numbers from each index i to the end of the array.
Initialize Answer and Prefix Variables:
- Start with ans as the product of suf_gcd[0] and suf_lcm[0], which represents using all elements of the array without removal.
- Variables pre_gcd and pre_lcm are set to zero and one, respectively, to handle prefix calculations, representing the GCD and LCM of numbers from the start of the array up to, but not including, the current element i.
Iterate Over the Array:
- For each element, calculate potential factor scores by considering the array without that element:
  - current_factor_score = gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1])
- Update ans to the maximum of itself and current_factor_score.
- Update the prefix GCD and LCM:
  - pre_gcd = gcd(pre_gcd, x)
  - pre_lcm = lcm(pre_lcm, x)
Return the Maximum Factor Score:
- After evaluating the removal impact for each element, return the highest score found.

The approach efficiently balances computational cost by leveraging the characteristics of GCD and LCM and their associative properties, ensuring that each potential element removal is considered without redundant calculations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example using the given solution approach to ensure clarity. Consider the array nums = [2, 3, 4].

Initialize Arrays:
- Initialize suf_gcd and suf_lcm with appropriate base values:
  - suf_gcd = [0, 0, 0]
  - suf_lcm = [1, 1, 1]
Compute Suffix GCD and LCM:
- i = 2: suf_gcd[2] = gcd(0, 4) = 4, suf_lcm[2] = lcm(1, 4) = 4
- i = 1: suf_gcd[1] = gcd(4, 3) = 1, suf_lcm[1] = lcm(4, 3) = 12
- i = 0: suf_gcd[0] = gcd(1, 2) = 1, suf_lcm[0] = lcm(12, 2) = 12
- Suffix arrays now look like: suf_gcd = [1, 1, 4], suf_lcm = [12, 12, 4]
Initialize Answer and Prefix Variables:
- Set ans to the product of suf_gcd[0] and suf_lcm[0]: ans = 1 * 12 = 12
- Initialize pre_gcd = 0 and pre_lcm = 1
Iterate Over the Array:
- i = 0:
  - Removal contribution: current_factor_score = gcd(0, 1) * lcm(1, 12) = 1 * 12 = 12
  - Update ans to max(12, 12) = 12
  - Update pre_gcd = gcd(0, 2) = 2, pre_lcm = lcm(1, 2) = 2
- i = 1:
  - Removal contribution: current_factor_score = gcd(2, 4) * lcm(2, 4) = 2 * 4 = 8
  - Update ans to max(12, 8) = 12
  - Update pre_gcd = gcd(2, 3) = 1, pre_lcm = lcm(2, 3) = 6
- i = 2:
  - Removal contribution: current_factor_score = gcd(1, 0) * lcm(6, 1) = 1 * 6 = 6
  - Update ans to max(12, 6) = 12
  - Update pre_gcd = gcd(1, 4) = 1, pre_lcm = lcm(6, 4) = 12
Return the Maximum Factor Score:
- The maximum factor score observed is 12.

This walkthrough illustrates how the solution efficiently computes potential scores through iterative prefix and suffix calculations, ensuring maximum efficiency.

Solution Implementation

1from typing import List
2from math import gcd
3from math import lcm
4
5class Solution:
6    def maxScore(self, nums: List[int]) -> int:
7        n = len(nums)
8      
9        # Initialize arrays for suffix GCD and LCM
10        suf_gcd = [0] * (n + 1)
11        suf_lcm = [0] * n + [1]
12      
13        # Calculate suffix GCD and LCM
14        for i in range(n - 1, -1, -1):
15            suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
16            suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i])
17
18        # Compute initial answer based on the first suffix GCD and LCM
19        ans = suf_gcd[0] * suf_lcm[0]
20      
21        # Initialize prefix GCD and LCM
22        pre_gcd, pre_lcm = 0, 1
23      
24        # Iterate over each number in the list
25        for i, num in enumerate(nums):
26            # Update the maximum score considering the split at current index
27            ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]))
28          
29            # Update prefix GCD and LCM
30            pre_gcd = gcd(pre_gcd, num)
31            pre_lcm = lcm(pre_lcm, num)
32      
33        return ans
34

1class Solution {
2  
3    public long maxScore(int[] nums) {
4        int n = nums.length;
5      
6        // Suffix GCD and LCM arrays
7        long[] sufGcd = new long[n + 1];
8        long[] sufLcm = new long[n + 1];
9      
10        // Initialize suffix LCM for the last element
11        sufLcm[n] = 1;
12      
13        // Compute the suffix GCD and LCM for each position
14        for (int i = n - 1; i >= 0; --i) {
15            // GCD of the current suffix
16            sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
17          
18            // LCM of the current suffix
19            sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
20        }
21      
22        // Calculate the maximum score starting with sufGcd[0] * sufLcm[0]
23        long maxScore = sufGcd[0] * sufLcm[0];
24      
25        // Initialize prefix GCD and LCM
26        long preGcd = 0, preLcm = 1;
27      
28        // Iterate through the array to calculate maximum score
29        for (int i = 0; i < n; ++i) {
30            // Calculate potential score using current prefix GCD/LCM and suffix GCD/LCM
31            long currentScore = gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]);
32            maxScore = Math.max(maxScore, currentScore);
33          
34            // Update prefix GCD and LCM for the next iteration
35            preGcd = gcd(preGcd, nums[i]);
36            preLcm = lcm(preLcm, nums[i]);
37        }
38      
39        return maxScore;
40    }
41
42    // Helper function to compute GCD of two numbers
43    private long gcd(long a, long b) {
44        return b == 0 ? a : gcd(b, a % b);
45    }
46
47    // Helper function to compute LCM of two numbers
48    private long lcm(long a, long b) {
49        return a / gcd(a, b) * b;
50    }
51}
52

1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5class Solution {
6public:
7    long long maxScore(std::vector<int>& nums) {
8        int size = nums.size();
9      
10        // Initialize suffix GCD and LCM vectors
11        std::vector<long long> suffixGCD(size + 1, 0);
12        std::vector<long long> suffixLCM(size + 1, 1);
13
14        // Calculate suffix GCDs and LCMs
15        for (int i = size - 1; i >= 0; --i) {
16            suffixGCD[i] = std::gcd(suffixGCD[i + 1], nums[i]); // Update suffix GCD
17            suffixLCM[i] = std::lcm(suffixLCM[i + 1], nums[i]); // Update suffix LCM
18        }
19
20        // Initialize answer with entire range GCD * LCM
21        long long answer = suffixGCD[0] * suffixLCM[0];
22      
23        // Initialize prefix GCD and LCM
24        long long prefixGCD = 0, prefixLCM = 1;
25
26        // Compute the maximum score by iterating through elements
27        for (int i = 0; i < size; ++i) {
28            // Calculate the score for the current split
29            long long currentScore = std::gcd(prefixGCD, suffixGCD[i + 1]) * std::lcm(prefixLCM, suffixLCM[i + 1]);
30            answer = std::max(answer, currentScore);
31          
32            // Update prefix GCD and LCM with current element
33            prefixGCD = std::gcd(prefixGCD, nums[i]);
34            prefixLCM = std::lcm(prefixLCM, nums[i]);
35        }
36      
37        return answer; // Return the maximum score
38    }
39};
40

1// Function to calculate the maximum score using the provided logic
2function maxScore(nums: number[]): number {
3    const n = nums.length;
4
5    // Arrays to maintain suffix GCD and suffix LCM values
6    const sufGcd: number[] = Array(n + 1).fill(0);
7    const sufLcm: number[] = Array(n + 1).fill(1);
8
9    // Populate suffix GCD and LCM starting from the end of the array
10    for (let i = n - 1; i >= 0; i--) {
11        sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
12        sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
13    }
14
15    // Initialize the answer with the product of the entire array's GCD and LCM
16    let ans = sufGcd[0] * sufLcm[0];
17
18    // Variables to maintain prefix GCD and LCM as we traverse the array
19    let preGcd = 0,
20        preLcm = 1;
21
22    // Traverse the array to consider each possible partition
23    for (let i = 0; i < n; i++) {
24        // Calculate the score for current partition and maximize the answer
25        ans = Math.max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
26
27        // Update the prefix GCD and LCM with the current number
28        preGcd = gcd(preGcd, nums[i]);
29        preLcm = lcm(preLcm, nums[i]);
30    }
31    return ans;
32}
33
34// Helper function to compute the greatest common divisor
35function gcd(a: number, b: number): number {
36    return b === 0 ? a : gcd(b, a % b);
37}
38
39// Helper function to compute the least common multiple
40function lcm(a: number, b: number): number {
41    return (a / gcd(a, b)) * b;
42}
43

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the algorithm involves iterating over the list a few times: once for computing suffix GCD and LCM values and once more for calculating the maximum score using prefix and suffix values.

The space complexity of the code is O(n) as well. This is due to the additional arrays suf_gcd and suf_lcm that are created to store the suffix GCD and LCM values, which require space proportional to the input list size.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: