Find the Maximum Factor Score of Array

• 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.

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.

1class Solution {2    private long gcd(long a, long b) {3        while (b != 0) {4            long temp = b;5            b = a % b;6            a = temp;7        }8        return a;9    }10 11    private long lcm(long a, long b) {12        if (a == 0 || b == 0) return 0;13        if (a == 1) return b;14        if (b == 1) return a;15        return (a / gcd(a, b)) * b; // Divide first to prevent overflow16    }17 18    public int maxFactorScore(int[] nums) {19        int n = nums.length;20        if (n == 1) {21            long val = nums[0];22            return (int) (val * val);23        }24 25        long[] prefixGcd = new long[n];26        long[] suffixGcd = new long[n];27        long[] prefixLcm = new long[n];28        long[] suffixLcm = new long[n];29 30        // Populate prefix arrays31        prefixGcd[0] = nums[0];32        prefixLcm[0] = nums[0];33        for (int i = 1; i < n; i++) {34            prefixGcd[i] = gcd(prefixGcd[i - 1], nums[i]);35            prefixLcm[i] = lcm(prefixLcm[i - 1], nums[i]);36        }37 38        // Populate suffix arrays39        suffixGcd[n - 1] = nums[n - 1];40        suffixLcm[n - 1] = nums[n - 1];41        for (int i = n - 2; i >= 0; i--) {42            suffixGcd[i] = gcd(suffixGcd[i + 1], nums[i]);43            suffixLcm[i] = lcm(suffixLcm[i + 1], nums[i]);44        }45 46        // Case 1: No removal47        long maxScore = prefixGcd[n - 1] * prefixLcm[n - 1];48 49        // Case 2: One element removed50        for (int i = 0; i < n; i++) {51            long currentGcd, currentLcm;52            if (i == 0) { // Remove first element53                currentGcd = suffixGcd[1];54                currentLcm = suffixLcm[1];55            } else if (i == n - 1) { // Remove last element56                currentGcd = prefixGcd[n - 2];57                currentLcm = prefixLcm[n - 2];58            } else { // Remove middle element59                currentGcd = gcd(prefixGcd[i - 1], suffixGcd[i + 1]);60                currentLcm = lcm(prefixLcm[i - 1], suffixLcm[i + 1]);61            }62            maxScore = Math.max(maxScore, currentGcd * currentLcm);63        }64 65        return (int) maxScore;66    }67}

• 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.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    private long gcd(long a, long b) {6        while (b != 0) {7            long temp = b;8            b = a % b;9            a = temp;10        }11        return a;12    }13 14    private long lcm(long a, long b) {15        if (a == 0 || b == 0) return 0;16        if (a == 1) return b;17        if (b == 1) return a;18        return (a / gcd(a, b)) * b; // Divide first to prevent overflow19    }20 21    private long calculateScore(List<Integer> list) {22        if (list.isEmpty()) {23            return 0;24        }25        if (list.size() == 1) {26            long val = list.get(0);27            return val * val;28        }29        long currentGcd = list.get(0);30        long currentLcm = list.get(0);31        for (int i = 1; i < list.size(); i++) {32            currentGcd = gcd(currentGcd, list.get(i));33            currentLcm = lcm(currentLcm, list.get(i));34        }35        return currentGcd * currentLcm;36    }37 38    public int maxFactorScore(int[] nums) {39        long maxScore = 0;40        int n = nums.length;41 42        // Case 1: No element removed43        List<Integer> fullList = new ArrayList<>();44        for (int num : nums) {45            fullList.add(num);46        }47        maxScore = calculateScore(fullList);48 49        // Case 2: One element removed50        if (n > 1) {51            for (int i = 0; i < n; i++) {52                List<Integer> subList = new ArrayList<>();53                for (int j = 0; j < n; j++) {54                    if (i != j) {55                        subList.add(nums[j]);56                    }57                }58                maxScore = Math.max(maxScore, calculateScore(subList));59            }60        }61 62        return (int) maxScore;63    }64}