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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


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

1
2
3
4


Input: nums = [3]

Output: 9

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 30

Solution

Method 1 – GCD and LCM with One Removal

Intuition

The factor score is the product of the GCD and LCM of the array. To maximize the score after removing at most one element, we can try removing each element (including removing none) and compute the GCD and LCM for the resulting array.

Approach

  1. For each index (including the case where no element is removed):
    • Remove the element at that index (or none).
    • Compute the GCD and LCM of the remaining elements.
    • Calculate the factor score as GCD * LCM.
  2. Track the maximum factor score found.
  3. Return the maximum score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxFactorScore(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for(int i = -1; i < n; ++i) {
            int g = 0, l = 1;
            for(int j = 0; j < n; ++j) if(j != i) {
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
            }
            if(n == 1 && i == -1) ans = nums[0]*nums[0];
            else if(n == 1 && i == 0) ans = 0;
            else ans = max(ans, g * l);
        }
        return ans;
    }
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
    int lcm(int a, int b) { return a / gcd(a, b) * b; }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func maxFactorScore(nums []int) int {
    n, ans := len(nums), 0
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    lcm := func(a, b int) int {
        return a / gcd(a, b) * b
    }
    for i := -1; i < n; i++ {
        g, l := 0, 1
        for j := 0; j < n; j++ {
            if j != i {
                g = gcd(g, nums[j])
                l = lcm(l, nums[j])
            }
        }
        if n == 1 && i == -1 {
            ans = nums[0] * nums[0]
        } else if n == 1 && i == 0 {
            ans = 0
        } else if g*l > ans {
            ans = g * l
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxFactorScore(int[] nums) {
        int n = nums.length, ans = 0;
        for(int i = -1; i < n; ++i) {
            int g = 0, l = 1;
            for(int j = 0; j < n; ++j) if(j != i) {
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
            }
            if(n == 1 && i == -1) ans = nums[0]*nums[0];
            else if(n == 1 && i == 0) ans = 0;
            else ans = Math.max(ans, g * l);
        }
        return ans;
    }
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    int lcm(int a, int b) { return a / gcd(a, b) * b; }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maxFactorScore(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        fun lcm(a: Int, b: Int): Int = a / gcd(a, b) * b
        for (i in -1 until n) {
            var g = 0; var l = 1
            for (j in 0 until n) if (j != i) {
                g = gcd(g, nums[j])
                l = lcm(l, nums[j])
            }
            if (n == 1 && i == -1) ans = nums[0]*nums[0]
            else if (n == 1 && i == 0) ans = 0
            else ans = maxOf(ans, g * l)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxFactorScore(self, nums: list[int]) -> int:
        from math import gcd
        def lcm(a: int, b: int) -> int:
            return a * b // gcd(a, b) if a and b else a or b
        n = len(nums)
        ans = 0
        for i in range(-1, n):
            g, l = 0, 1
            for j in range(n):
                if j != i:
                    g = gcd(g, nums[j])
                    l = lcm(l, nums[j])
            if n == 1 and i == -1:
                ans = nums[0]*nums[0]
            elif n == 1 and i == 0:
                ans = 0
            else:
                ans = max(ans, g*l)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

impl Solution {
    pub fn max_factor_score(nums: Vec<i32>) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        fn lcm(a: i32, b: i32) -> i32 {
            if a == 0 || b == 0 { a.max(b) } else { a / gcd(a, b) * b }
        }
        let n = nums.len();
        let mut ans = 0;
        for i in -1i32..n as i32 {
            let mut g = 0;
            let mut l = 1;
            for j in 0..n {
                if j as i32 != i {
                    g = gcd(g, nums[j]);
                    l = lcm(l, nums[j]);
                }
            }
            if n == 1 && i == -1 {
                ans = nums[0]*nums[0];
            } else if n == 1 && i == 0 {
                ans = 0;
            } else {
                ans = ans.max(g*l);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    maxFactorScore(nums: number[]): number {
        const gcd = (a: number, b: number): number => b ? gcd(b, a % b) : a;
        const lcm = (a: number, b: number): number => a && b ? a / gcd(a, b) * b : a || b;
        let ans = 0, n = nums.length;
        for(let i=-1;i<n;++i) {
            let g = 0, l = 1;
            for(let j=0;j<n;++j) if(j!==i) {
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
            }
            if(n===1 && i===-1) ans = nums[0]*nums[0];
            else if(n===1 && i===0) ans = 0;
            else ans = Math.max(ans, g*l);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 log M), where n is the length of nums and M is the maximum value in nums (for GCD/LCM).
  • 🧺 Space complexity: O(1), only a few variables are used.