# Maximum Element-Sum of a Complete Subset of Indices
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-element-sum-of-a-complete-subset-of-indices)
Canonical: https://scaleengineer.com/dsa/problems/maximum-element-sum-of-a-complete-subset-of-indices
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
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_.

**Example 1:**

**Input:** nums = \[8,7,3,5,7,2,4,9\]

**Output:** 16

**Explanation:**

We select elements at indices 2 and 8 and `2 * 8` is a perfect square.

**Example 2:**

**Input:** nums = \[8,10,3,8,1,13,7,9,4\]

**Output:** 20

**Explanation:**

We select elements at indices 1, 4, and 9\. `1 * 4`, `1 * 9`, `4 * 9` are perfect squares.

**Constraints:**

* `1 <= n == nums.length <= 104`
* `1 <= nums[i] <= 109`

# Approaches
## Grouping by Square-Free Core (Iterative Calculation)
This approach solves the problem by identifying the fundamental property of the complete subset: all indices in such a subset must share the same 'square-free part'. It iterates through each index, calculates this property, and groups the corresponding `nums` values. A hash map is used to keep track of the sum of elements for each group. The final answer is the largest sum found among all groups.
**Time:** O(n * sqrt(n)) - The main loop runs `n` times. Inside the loop, the `getSquareFreePart(i)` function takes roughly `O(sqrt(i))` time. The total time complexity is the sum of `sqrt(i)` for `i` from 1 to `n`, which is approximated by the integral of `sqrt(x)`, resulting in `O(n^(3/2))` or `O(n * sqrt(n))`. For `n=10^4`, this is about `10^6` operations, which is acceptable. · **Space:** O(n) - In the worst-case scenario, every index from 1 to n could have a unique square-free part, requiring the hash map to store up to `n` entries.
**Pros:** The logic is straightforward and directly follows from the mathematical property.; It's relatively easy to implement without complex data structures.
**Cons:** The time complexity of `O(n * sqrt(n))` can be slow, although it passes for the given constraints (`n <= 10^4`).; It performs redundant computations, as the square-free part of a number is calculated independently each time.
### Explanation
The problem requires finding a subset of indices where the product of any pair is a perfect square. This property is equivalent to all indices in the subset having the same square-free core. For example, `sf(8) = 2` (since `8 = 4 * 2`) and `sf(2) = 2`. Thus, indices 2 and 8 can be in the same set, as `2 * 8 = 16` is a perfect square.

This method directly implements this logic:
1.  Initialize a `HashMap<Integer, Long>` called `groupSums` to map a square-free core to the sum of `nums` values for all indices sharing that core.
2.  Iterate with an index `i` from `1` to `n` (where `n` is the length of `nums`).
3.  For each `i`, calculate its square-free part. This is done in a helper function, `getSquareFreePart(i)`, which works by trial division. It iterates from `d = 2` up to `sqrt(i)` and for each `d`, it divides `i` by `d*d` as many times as possible.
4.  Retrieve the value `nums[i-1]` (using `i-1` for 0-based array access).
5.  Add this value to the running sum for the calculated square-free part in the `groupSums` map.
6.  After the loop finishes, iterate through the values of the `groupSums` map to find the maximum sum.
7.  Return this maximum sum.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    /**
     * Calculates the square-free part of a number n.
     * A number's square-free part is what remains after dividing out all perfect square factors.
     * Example: sf(72) -> 72 = 36 * 2 -> sf is 2.
     */
    private int getSquareFreePart(int n) {
        int num = n;
        for (int i = 2; i * i <= num; i++) {
            // If i*i is a factor, divide it out completely.
            while (num % (i * i) == 0) {
                num /= (i * i);
            }
        }
        return num;
    }

    public long maximumSum(int[] nums) {
        int n = nums.length;
        Map<Integer, Long> groupSums = new HashMap<>();
        
        // Iterate through 1-based indices
        for (int i = 1; i <= n; i++) {
            int core = getSquareFreePart(i);
            long currentVal = nums[i - 1];
            groupSums.put(core, groupSums.getOrDefault(core, 0L) + currentVal);
        }
        
        long maxSum = 0;
        for (long sum : groupSums.values()) {
            maxSum = Math.max(maxSum, sum);
        }
        
        return maxSum;
    }
}
```
### Algorithm
- The core idea is that for any two indices `i` and `j` in a valid subset, the product `i * j` must be a perfect square.
- This condition holds if and only if `i` and `j` have the same **square-free part**. The square-free part of a number is the number itself divided by the largest perfect square that divides it (e.g., for `12 = 4 * 3`, the square-free part is `3`).
- This observation allows us to partition all indices from `1` to `n` into groups based on their square-free part.
- To get the maximum sum, we should find the sum of elements for each group and then take the maximum among all these group sums.
- This approach iterates through each index `i` from `1` to `n`, calculates its square-free part on the fly, and uses a hash map to maintain the sum for each group.

## Optimized Grouping using a Sieve
This is an optimized version of the first approach. It recognizes that calculating the square-free part for each index from scratch is inefficient. By precomputing the square-free parts for all numbers from 1 to `n` using a sieve, we can reduce the time complexity significantly. The sieve efficiently removes all perfect square factors from each number in nearly linear time. Once the precomputation is done, the problem is solved by grouping and summing the elements, just like in the previous approach, but with a much faster lookup for the square-free parts.
**Time:** O(n log log n) - The sieve precomputation step runs in `O(n log log n)` or `O(n)` time, which is much faster than `O(n * sqrt(n))`. The summation part runs in `O(n)`. Therefore, the total time complexity is dominated by the sieve and is effectively linear. · **Space:** O(n) - This approach requires `O(n)` space for the `sf` array used in the sieve, plus `O(n)` space for the hash map in the worst case.
**Pros:** Highly efficient with a nearly linear time complexity.; Optimal solution for the given constraints.
**Cons:** Requires additional `O(n)` space for the sieve array.; The sieve logic, while efficient, can be slightly more complex to understand and implement compared to the direct calculation.
### Explanation
The bottleneck in the previous approach is the repeated calculation within the main loop. We can optimize this by pre-calculating all necessary square-free parts at once.

**Algorithm Steps:**
1.  **Precomputation with a Sieve:**
    - Create an integer array `sf` of size `n + 1`.
    - Initialize `sf[i] = i` for all `i` from `1` to `n`.
    - Iterate with a number `j` from `2` up to `n`. If `j*j > n`, we can stop.
    - For each `j`, let `square = j * j`.
    - Iterate through all multiples of `square` up to `n` (i.e., `m = square, 2*square, 3*square, ...`).
    - For each multiple `m`, repeatedly divide `sf[m]` by `square` until it's no longer divisible. This effectively removes the perfect square factor `j*j` from `sf[m]`.
2.  **Grouping and Summation:**
    - Initialize a `HashMap<Integer, Long>` called `groupSums`.
    - Iterate with an index `i` from `1` to `n`.
    - The square-free part of `i` is now a simple lookup: `core = sf[i]`.
    - Add `nums[i-1]` to the sum for the group `core` in the `groupSums` map.
3.  **Find Maximum:**
    - Find and return the maximum value present in the `groupSums` map.

This precomputation step changes the overall time complexity from `O(n * sqrt(n))` to nearly `O(n)`. 

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSum(int[] nums) {
        int n = nums.length;
        
        // Step 1: Precompute square-free parts for 1 to n using a sieve
        int[] sf = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sf[i] = i;
        }
        
        for (int j = 2; j * j <= n; j++) {
            int square = j * j;
            for (int m = square; m <= n; m += square) {
                while (sf[m] % square == 0) {
                    sf[m] /= square;
                }
            }
        }
        
        // Step 2: Group sums based on the precomputed square-free parts
        Map<Integer, Long> groupSums = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int core = sf[i]; // O(1) lookup
            long currentVal = nums[i - 1];
            groupSums.put(core, groupSums.getOrDefault(core, 0L) + currentVal);
        }
        
        // Step 3: Find the maximum sum among all groups
        long maxSum = 0;
        for (long sum : groupSums.values()) {
            maxSum = Math.max(maxSum, sum);
        }
        
        return maxSum;
    }
}
```
### Algorithm
- This approach uses the same fundamental principle of grouping indices by their square-free part.
- To improve efficiency, it avoids re-calculating the square-free part for each index individually.
- Instead, it precomputes the square-free parts for all numbers from `1` to `n` using a sieve-like algorithm.
- The sieve works by iterating through numbers `j` and for each `j`, removing the perfect square factor `j*j` from all its multiples up to `n`.
- After this `O(n)` precomputation, the main logic proceeds as before: iterate through indices, look up the precomputed square-free part, and aggregate sums in a hash map.

# Solutions
### Java

```java
class Solution {
public
  long maximumSum(List<Integer> nums) {
    long ans = 0;
    int n = nums.size();
    boolean[] used = new boolean[n + 1];
    int bound = (int)Math.floor(Math.sqrt(n));
    int[] squares = new int[bound + 1];
    for (int i = 1; i <= bound + 1; i++) {
      squares[i - 1] = i * i;
    }
    for (int i = 1; i <= n; i++) {
      long res = 0;
      int idx = 0;
      int curr = i * squares[idx];
      while (curr <= n) {
        res += nums.get(curr - 1);
        curr = i * squares[++idx];
      }
      ans = Math.max(ans, res);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSum(vector<int> &nums) {
    long long ans = 0;
    int n = nums.size();
    for (int k = 1; k <= n; ++k) {
      long long t = 0;
      for (int j = 1; k * j * j <= n; ++j) {
        t += nums[k * j * j - 1];
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSum(self, nums: List[int]) -> int: n = len(nums) ans = 0 for k in range(1, n + 1): t = 0 j = 1 while k * j * j <= n: t += nums[k * j * j - 1] j += 1 ans = max(ans, t) return ans

```