# 2862. Maximum Element-Sum of a Complete Subset of Indices

## Problem Statement

<br>

You are given a **1-indexed** array `nums` of `n` integers.

A set of numbers is **complete** if the product of every pair of its elements is a perfect square.

For a subset of the indices set `{1, 2, ..., n}` represented as `{i1, i2, ..., ik}`, we define its **element-sum** as: `nums[i1] + nums[i2] + ... + nums[ik]`.

Return *the **maximum element-sum** of a **complete** subset of the indices set* `{1, 2, ..., n}`.

A perfect square is a number that can be expressed as the product of an integer by itself.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [8,7,3,5,7,2,4,9]
</strong><strong>Output: 16
</strong><strong>Explanation: Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
</strong>The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 8 + 5 = 13.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 7 + 9 = 16.
Hence, the maximum element-sum of a complete subset of indices is 16.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [5,10,3,10,1,13,7,9,4]
</strong><strong>Output: 19
</strong><strong>Explanation: Apart from the subsets consisting of a single index, there are four other complete subsets of indices: {1,4}, {1,9}, {2,8}, {4,9}, and {1,4,9}.
</strong>The sum of the elements conrresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
The sum of the elements conrresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
The sum of the elements conrresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
The sum of the elements conrresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
The sum of the elements conrresponding to indices 1, 4, and 9 is equal to nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19.
Hence, the maximum element-sum of a complete subset of indices is 19.
</code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

We tend to eliminate the perfect squares repeatedly
Eg->
nums  8,7,3,5,7,2,4,9
index 0 1 2 3 4 5 6 7

take ->   4/(4) -> 1 

1 4 9
1 ->will be saved
4/4 -> will be added to 1
9/9 -> will be added to 1


We take all perfect squares until number (index)
And remove till we get a residue 
Which is not a perfect square

Then we have another number , With same residue , Which will be added to that to make
It a perfect square

eg->

24 -> 4*6 , We need extra 6 
```

### Links

<https://leetcode.com/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/>

### Video Links

<https://www.youtube.com/watch?v=wlaDBN_CJKg&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    long long maximumSum(vector<int>& nums) {
        unordered_map<int, long long> count;
        long long res = 0;

        for(int i=0; i<nums.size(); i++){
            long long num = i+1;
            for(long long v=2; v*v<=num; v++){
                while(num % (v*v) == 0)
                    num /= v*v;
            }

            res = max(res, count[num] += nums[i]);
        }

        return res;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/array/hard/2862.-maximum-element-sum-of-a-complete-subset-of-indices.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.