Maximum Element-Sum of a Complete Subset of Indices

Maximum Element-Sum of a Complete Subset of Indices - Problem

You are given a 1-indexed array nums of positive integers. Your task is to select a complete subset from nums where every pair of selected indices when multiplied together results in a perfect square.

More formally, if you select indices i and j, then i * j must be a perfect square.

Return the sum of the complete subset with the maximum sum.

Input & Output

Example 1 — Basic Case

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

› Output: 16

💡 Note: Indices 2 and 8 have square-free part 2, so 2×8=16 is a perfect square. Their values are 7+9=16, which is the maximum.

Example 2 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Only one element, so the subset contains just index 1 with value 5.

Example 3 — Multiple Groups

$ Input: nums = [1,4,3,3,2]

› Output: 6

💡 Note: Indices 3 and 4 both have square-free part 3, values 3+3=6. Index 1 has square-free 1 (value 1), index 2 has square-free 2 (value 4), index 5 has square-free 5 (value 2).

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[8,7,3,5,7,2,4,9] with 1-indexed positions

Process

Group indices by square-free parts: same square-free → compatible

Output

Maximum sum is 16 from indices 2,8 (values 7,9)

Key Takeaway

🎯 Key Insight: Two indices can be in the same complete subset if they have identical square-free parts

Asked in

G Google 15 f Meta 8

The key insight is that two indices i and j can be in the same complete subset if and only if i×j is a perfect square, which happens when they have the same square-free part. Best approach is Mathematical Grouping with Time: O(n×√max_index), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Grouping	O(n × √max_index)	O(n)	Group indices by their square-free factors to find compatible sets efficiently
Brute Force - Try All Subsets	O(n × 2ⁿ)	O(n)	Generate all possible subsets and check if each forms a complete subset

Mathematical Grouping — Algorithm Steps

Calculate square-free part for each index
Group indices with same square-free part
Find maximum sum among all groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Square-Free

For each index, find its square-free part

Group Indices

Group indices with identical square-free parts

Find Maximum

Return sum of the largest group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_GROUPS 1000

struct Group {
    int key;
    long long sum;
};

int getSquareFree(int n) {
    int result = 1;
    int i = 2;
    while (i * i <= n) {
        int count = 0;
        while (n % i == 0) {
            n /= i;
            count++;
        }
        if (count % 2 == 1) {
            result *= i;
        }
        i++;
    }
    if (n > 1) {
        result *= n;
    }
    return result;
}

long long solution(int* nums, int n) {
    struct Group groups[MAX_GROUPS];
    int groupCount = 0;
    
    // Group indices by their square-free part
    for (int i = 0; i < n; i++) {
        int index = i + 1; // 1-indexed
        int squareFree = getSquareFree(index);
        
        // Find existing group or create new one
        int found = -1;
        for (int j = 0; j < groupCount; j++) {
            if (groups[j].key == squareFree) {
                found = j;
                break;
            }
        }
        
        if (found >= 0) {
            groups[found].sum += nums[i];
        } else {
            groups[groupCount].key = squareFree;
            groups[groupCount].sum = nums[i];
            groupCount++;
        }
    }
    
    // Find maximum sum among all groups
    long long maxSum = 0;
    for (int i = 0; i < groupCount; i++) {
        if (groups[i].sum > maxSum) {
            maxSum = groups[i].sum;
        }
    }
    
    return maxSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array
    int nums[50];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × √max_index)

For each of n indices, compute square-free part in O(√i) time

✓ Linear Growth

Space Complexity

O(n)

Hash map to group indices by square-free part, stores at most n entries

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler