# Find the Maximum Factor Score of Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-factor-score-of-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-factor-score-of-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
**Companies:** [Info Edge](https://scaleengineer.com/companies/info-edge)
---
## Problem
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.

**Example 1:**

**Input:** nums = \[2,4,8,16\]

**Output:** 64

**Explanation:**

On removing 2, the GCD of the rest of the elements is 4 while the LCM is 16, which gives a maximum factor score of `4 * 16 = 64`.

**Example 2:**

**Input:** nums = \[1,2,3,4,5\]

**Output:** 60

**Explanation:**

The maximum factor score of 60 can be obtained without removing any elements.

**Example 3:**

**Input:** nums = \[3\]

**Output:** 9

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 30`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. We consider every possible scenario: either not removing any element or removing exactly one element from the array. For each of these `n+1` scenarios, where `n` is the length of the array, we form the resulting subarray and calculate its factor score. The maximum score found across all scenarios is the answer.
**Time:** O(N^2 * log(M)), where N is the number of elements in `nums` and M is the maximum value in `nums`. For each of the `N+1` subarrays, we iterate through its elements (up to `N`) to compute GCD and LCM. Each GCD/LCM operation takes `O(log(M))` time. · **Space:** O(N), where N is the number of elements in `nums`. This space is used to store the temporary subarray in each iteration of the main loop.
**Pros:** Simple to understand and implement.; Directly follows the problem definition, making it less prone to logical errors.
**Cons:** Inefficient due to redundant calculations. For each subarray, GCD and LCM are computed from scratch, leading to a quadratic time complexity.
### Explanation
The core of this method is to iterate through all `n+1` possibilities.

First, we calculate the factor score for the original array without any removals. This serves as our initial maximum score.

Then, we loop from `i = 0` to `n-1`. In each iteration `i`, we simulate the removal of the element `nums[i]`. To do this, we construct a temporary subarray that contains all elements of `nums` except for `nums[i]`. For this temporary subarray, we calculate its Greatest Common Divisor (GCD) and Least Common Multiple (LCM).

The GCD can be found by iteratively applying the Euclidean algorithm to all elements of the subarray. The LCM can be found similarly, using the formula `lcm(a, b) = (a * b) / gcd(a, b)`. It's important to use 64-bit integers (`long` in Java) for LCM and score calculations to prevent overflow, as intermediate values can become very large even if the final answer fits in a 32-bit integer.

The factor score for this subarray is `GCD * LCM`. We compare this score with our current maximum score and update it if the new score is greater. After checking all `n` possible removals, the final maximum score is our result.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        if (a == 1) return b;
        if (b == 1) return a;
        return (a / gcd(a, b)) * b; // Divide first to prevent overflow
    }

    private long calculateScore(List<Integer> list) {
        if (list.isEmpty()) {
            return 0;
        }
        if (list.size() == 1) {
            long val = list.get(0);
            return val * val;
        }
        long currentGcd = list.get(0);
        long currentLcm = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            currentGcd = gcd(currentGcd, list.get(i));
            currentLcm = lcm(currentLcm, list.get(i));
        }
        return currentGcd * currentLcm;
    }

    public int maxFactorScore(int[] nums) {
        long maxScore = 0;
        int n = nums.length;

        // Case 1: No element removed
        List<Integer> fullList = new ArrayList<>();
        for (int num : nums) {
            fullList.add(num);
        }
        maxScore = calculateScore(fullList);

        // Case 2: One element removed
        if (n > 1) {
            for (int i = 0; i < n; i++) {
                List<Integer> subList = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        subList.add(nums[j]);
                    }
                }
                maxScore = Math.max(maxScore, calculateScore(subList));
            }
        }

        return (int) maxScore;
    }
}
```
### Algorithm
*   Initialize a variable `maxScore` to 0, using a `long` type to prevent overflow during intermediate calculations.
*   Define helper functions `gcd(a, b)` and `lcm(a, b)`. The `lcm` function should handle potential overflows by using `long` arithmetic.
*   First, consider the case where no element is removed. Create a list from the input `nums` array.
*   Calculate the GCD and LCM of all elements in this list. The factor score is their product. Update `maxScore` with this score.
*   Iterate through the `nums` array with an index `i` from `0` to `n-1`.
*   In each iteration, create a new temporary list containing all elements of `nums` except `nums[i]`.
*   If the temporary list is not empty, calculate its GCD and LCM, and then its factor score.
*   Update `maxScore = Math.max(maxScore, newScore)`.
*   After the loop finishes, `maxScore` holds the maximum possible factor score.
*   Cast the final `maxScore` to `int` and return it.

## Optimized Approach using Prefix and Suffix Arrays
This approach improves upon the brute-force method by avoiding redundant computations. The key idea is to precompute the GCD and LCM of all prefixes and suffixes of the array. With these precomputed values, we can find the GCD and LCM of any subarray (formed by removing one element) in constant time (plus the time for a single GCD/LCM operation).
**Time:** O(N * log(M)), where N is the number of elements and M is the maximum value. Populating the prefix/suffix arrays takes `O(N * log(M))`. The final loop to check all removal scenarios also takes `O(N * log(M))` because each `lcm`/`gcd` call is `O(log(M))`. This is a major improvement over the brute-force approach. · **Space:** O(N), where N is the number of elements in `nums`. This space is used for the four prefix and suffix arrays.
**Pros:** Significantly more efficient than the brute-force approach.; Reduces the overall time complexity from quadratic to linearithmic.
**Cons:** Requires extra space proportional to the input size to store the prefix and suffix arrays.; The implementation is slightly more complex than the brute-force approach.
### Explanation
When an element `nums[i]` is removed, the remaining elements form two contiguous blocks: `nums[0...i-1]` and `nums[i+1...n-1]`. The GCD of the new subarray is `GCD(GCD of nums[0...i-1], GCD of nums[i+1...n-1])`. A similar property holds for the LCM.

This observation allows us to use precomputation. We create four arrays:
*   `prefixGcd[i]`: GCD of `nums[0]` through `nums[i]`.
*   `suffixGcd[i]`: GCD of `nums[i]` through `nums[n-1]`.
*   `prefixLcm[i]`: LCM of `nums[0]` through `nums[i]`.
*   `suffixLcm[i]`: LCM of `nums[i]` through `nums[n-1]`.

These arrays can be populated in `O(N * log(M))` time. For example, `prefixGcd[i] = gcd(prefixGcd[i-1], nums[i])`.

After precomputation, we first calculate the score for the full array (`suffixGcd[0] * suffixLcm[0]`). Then, we iterate from `i = 0` to `n-1` to consider removing `nums[i]`. For each `i`, the GCD and LCM of the remaining elements are found by combining the corresponding prefix and suffix values in `O(log(M))` time. This significantly speeds up the process compared to re-calculating from scratch each time.

```java
class Solution {
    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        if (a == 1) return b;
        if (b == 1) return a;
        return (a / gcd(a, b)) * b; // Divide first to prevent overflow
    }

    public int maxFactorScore(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            long val = nums[0];
            return (int) (val * val);
        }

        long[] prefixGcd = new long[n];
        long[] suffixGcd = new long[n];
        long[] prefixLcm = new long[n];
        long[] suffixLcm = new long[n];

        // Populate prefix arrays
        prefixGcd[0] = nums[0];
        prefixLcm[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixGcd[i] = gcd(prefixGcd[i - 1], nums[i]);
            prefixLcm[i] = lcm(prefixLcm[i - 1], nums[i]);
        }

        // Populate suffix arrays
        suffixGcd[n - 1] = nums[n - 1];
        suffixLcm[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixGcd[i] = gcd(suffixGcd[i + 1], nums[i]);
            suffixLcm[i] = lcm(suffixLcm[i + 1], nums[i]);
        }

        // Case 1: No removal
        long maxScore = prefixGcd[n - 1] * prefixLcm[n - 1];

        // Case 2: One element removed
        for (int i = 0; i < n; i++) {
            long currentGcd, currentLcm;
            if (i == 0) { // Remove first element
                currentGcd = suffixGcd[1];
                currentLcm = suffixLcm[1];
            } else if (i == n - 1) { // Remove last element
                currentGcd = prefixGcd[n - 2];
                currentLcm = prefixLcm[n - 2];
            } else { // Remove middle element
                currentGcd = gcd(prefixGcd[i - 1], suffixGcd[i + 1]);
                currentLcm = lcm(prefixLcm[i - 1], suffixLcm[i + 1]);
            }
            maxScore = Math.max(maxScore, currentGcd * currentLcm);
        }

        return (int) maxScore;
    }
}
```
### Algorithm
*   Handle the edge case where `n=1`. The score is `nums[0] * nums[0]`.
*   Create four arrays of size `n` to store prefix/suffix GCDs and LCMs: `prefixGcd`, `suffixGcd`, `prefixLcm`, `suffixLcm`. Use `long` type for LCM arrays to prevent overflow.
*   Calculate all prefix GCDs and LCMs. `prefixGcd[i]` is the GCD of `nums[0...i]`. `prefixLcm[i]` is the LCM of `nums[0...i]`. This takes a single pass from left to right.
*   Calculate all suffix GCDs and LCMs. `suffixGcd[i]` is the GCD of `nums[i...n-1]`. `suffixLcm[i]` is the LCM of `nums[i...n-1]`. This takes a single pass from right to left.
*   Calculate the factor score for the original array (no removals) using `prefixGcd[n-1]` and `prefixLcm[n-1]`. Initialize `maxScore` with this value.
*   Iterate with an index `i` from `0` to `n-1` to simulate removing `nums[i]`.
*   For each `i`, determine the GCD and LCM of the remaining elements using the precomputed arrays.
    *   If `i` is the first element, the new GCD/LCM are `suffixGcd[1]` and `suffixLcm[1]`.
    *   If `i` is the last element, they are `prefixGcd[n-2]` and `prefixLcm[n-2]`.
    *   Otherwise, they are `gcd(prefixGcd[i-1], suffixGcd[i+1])` and `lcm(prefixLcm[i-1], suffixLcm[i+1])`.
*   Calculate the factor score for this configuration and update `maxScore` if it's larger.
*   After the loop, cast the final `maxScore` to `int` and return it.

# Solutions
### Java

```java
class Solution {
public
  long maxScore(int[] nums) {
    int n = nums.length;
    long[] sufGcd = new long[n + 1];
    long[] sufLcm = new long[n + 1];
    sufLcm[n] = 1;
    for (int i = n - 1; i >= 0; --i) {
      sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
      sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
    }
    long ans = sufGcd[0] * sufLcm[0];
    long preGcd = 0, preLcm = 1;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans,
                     gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
      preGcd = gcd(preGcd, nums[i]);
      preLcm = lcm(preLcm, nums[i]);
    }
    return ans;
  }
private
  long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
private
  long lcm(long a, long b) { return a / gcd(a, b) * b; }
}

```

### Python

```python
class Solution:
    def maxScore(self, nums: List[int]) -> int: n = len(nums) suf_gcd = [0] * (n + 1) suf_lcm = [0] * n + [1] 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]) ans = suf_gcd[0] * suf_lcm[0] pre_gcd, pre_lcm = 0, 1 for i, x in enumerate(nums): ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1])) pre_gcd = gcd(pre_gcd, x) pre_lcm = lcm(pre_lcm, x) return ans

```

### CPP

```cpp
class Solution {
public:
  long long maxScore(vector<int> &nums) {
    int n = nums.size();
    vector<long long> sufGcd(n + 1, 0);
    vector<long long> sufLcm(n + 1, 1);
    for (int i = n - 1; i >= 0; --i) {
      sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
      sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
    }
    long long ans = sufGcd[0] * sufLcm[0];
    long long preGcd = 0, preLcm = 1;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
      preGcd = gcd(preGcd, nums[i]);
      preLcm = lcm(preLcm, nums[i]);
    }
    return ans;
  }
};

```