Find the Maximum Factor Score of Array

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

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

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;
    }
}