Find the maximum factor score of array

Array Math Number Theory

40.9% acceptance

Feb 23, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(nums: Vec<i32>) -> i64 {
    fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a } else { gcd(b, a % b) } }
    fn lcm(a: i64, b: i64) -> i64 { a / gcd(a, b) * b }
    
    let n = nums.len();
    
    // Prefix and suffix GCD and LCM
    let mut pre_gcd = vec![0i64; n + 1];
    let mut pre_lcm = vec![1i64; n + 1];
    let mut suf_gcd = vec![0i64; n + 1];
    let mut suf_lcm = vec![1i64; n + 1];
    
    for i in 0..n {
      pre_gcd[i + 1] = gcd(pre_gcd[i], nums[i] as i64);
      pre_lcm[i + 1] = lcm(pre_lcm[i], nums[i] as i64);
    }
    for i in (0..n).rev() {
      suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i] as i64);
      suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i] as i64);
    }
    
    // No removal
    let mut best = pre_gcd[n] * pre_lcm[n];
    
    // Remove element i
    for i in 0..n {
      let g = gcd(pre_gcd[i], suf_gcd[i + 1]);
      let l = lcm(pre_lcm[i], suf_lcm[i + 1]);
      best = best.max(g * l);
    }
    
    best
  }
}