Maximum element sum of a complete subset of indices

Array Math Number Theory

42.7% acceptance

Feb 25, 2026

233

You are given a 1-indexed array nums. Your task is to select a complete subset from nums where every pair of selected indices multiplied is a perfect square, i.e. if you select ai and aj, i * j must be a perfect square. Return the sum of the complete subset with the maximum sum.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum(nums: Vec<i32>) -> i64 {
    let _n = nums.len();
    // Two indices i, j are in same group iff square_free_part(i) == square_free_part(j)
    // square_free_part: remove all squared prime factors
    fn square_free(mut x: usize) -> usize {
      let mut res = 1;
      let mut d = 2;
      while d * d <= x {
        let mut cnt = 0;
        while x % d == 0 { x /= d; cnt += 1; }
        if cnt % 2 == 1 { res *= d; }
        d += 1;
      }
      if x > 1 { res *= x; }
      res
    }
    use std::collections::HashMap;
    let mut groups: HashMap<usize, i64> = HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      let idx = i + 1; // 1-indexed
      let key = square_free(idx);
      *groups.entry(key).or_insert(0) += v as i64;
    }
    *groups.values().max().unwrap_or(&0)
  }
}