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}