2862. Maximum Element-Sum of Indices Solution

The 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 a_i and a_j, 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 <= 10⁴
1 <= nums[i] <= 10⁹

Approach overview

Problem Overview: You are given an array nums indexed from 1. A subset of indices is considered complete if for every pair (i, j) in the subset, the product i * j is a perfect square. The goal is to choose such a subset and maximize the sum of the corresponding array values.

Approach 1: Factorization-Based Grouping (O(n log n) time, O(n) space)

The key observation comes from number theory. Two numbers produce a perfect square when multiplied if their prime factorizations have matching parity for every prime. This means their square-free kernel (the product of primes with odd exponent after removing square factors) must be identical. Iterate through indices i from 1 to n, compute the square‑free representation of i by removing squared prime factors, and use it as a grouping key. Accumulate nums[i-1] into a hash map keyed by this kernel. Every group represents indices that can form a complete subset because any pair within the group produces a perfect square product. The answer is the maximum accumulated sum among these groups. This approach combines array traversal with prime factorization techniques.

Approach 2: Graph Connectivity Concept (O(n sqrt(n)) time, O(n) space)

Another way to model the condition is through connectivity. Treat each index as a node in a graph. Connect i to indices of the form i * k^2 as long as they remain within bounds. Multiplying by a square preserves the square‑free kernel, which means all reachable nodes belong to the same valid subset. Starting from each index, perform DFS/BFS and collect all indices reachable via square multipliers. Sum the corresponding values in nums and track the maximum. This approach explicitly builds the relationship implied by the math property and is easier to reason about conceptually, though it is slower than the direct grouping method.

Recommended for interviews: The factorization-based grouping is the expected optimal solution. It shows understanding of the mathematical constraint behind perfect squares and avoids constructing explicit graph edges. The graph perspective helps build intuition, but the grouping solution demonstrates stronger algorithmic insight and cleaner implementation using math and hashing.

Approach 1: Approach 1: Factorization-Based Grouping

The goal is to group indices based on common factors from their prime factorizations. For two indices i and j, i * j is a perfect square if all primes in its factorization appear an even number of times. Use this property to group indices and compute the subset with the maximum sum.

Python

def max_element_sum(nums):
    max_sum = 0
    n = len(nums)
    for start in range(1, int(n**0.5) + 1):
        total = sum(nums[start-1:n:start])
        if total > max_sum:
            max_sum = total
    return max_sum

nums = [8, 10, 3, 8, 1, 13, 7, 9, 4]
print(max_element_sum(nums))

Java

import java.util.*;

public class Main {
    public static int maxElementSum(int[] nums) {
        int n = nums.length;
        int maxSum = 0;
        for (int start = 1; start * start <= n; start++) {
            int sum = 0;
            for (int i = start; i <= n; i += start) {
                sum += nums[i - 1];
            }
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
        System.out.println(maxElementSum(nums));
    }
}

C++

#include <iostream>
#include <cmath>
#include <vector>

int maxElementSum(const std::vector<int>& nums) {
    int n = nums.size();
    int maxSum = 0;
    for (int start = 1; start * start <= n; start++) {
        int sum = 0;
        for (int i = start; i <= n; i += start) {
            sum += nums[i - 1];
        }
        maxSum = std::max(maxSum, sum);
    }
    return maxSum;
}

int main() {
    std::vector<int> nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
    std::cout << maxElementSum(nums) << std::endl;
    return 0;
}

JavaScript

function maxElementSum(nums) {
    let maxSum = 0;
    const n = nums.length;
    for (let start = 1; start * start <= n; start++) {
        let sum = 0;
        for (let i = start; i <= n; i += start) {
            sum += nums[i - 1];
        }
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

const nums = [8, 10, 3, 8, 1, 13, 7, 9, 4];
console.log(maxElementSum(nums));

#include <stdio.h>
#include <math.h>

int maxElementSum(int* nums, int n) {
    int maxSum = 0;
    for (int start = 1; start * start <= n; start++) {
        int sum = 0;
        for (int i = start; i <= n; i += start) {
            sum += nums[i - 1];
        }
        if (sum > maxSum) {
            maxSum = sum;
        }
    }
    return maxSum;
}

int main() {
    int nums[] = {8, 10, 3, 8, 1, 13, 7, 9, 4};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", maxElementSum(nums, n));
    return 0;
}

using System;

class Program {
    static int MaxElementSum(int[] nums) {
        int n = nums.Length;
        int maxSum = 0;
        for (int start = 1; start * start <= n; start++) {
            int sum = 0;
            for (int i = start; i <= n; i += start) {
                sum += nums[i - 1];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return maxSum;
    }

    static void Main() {
        int[] nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
        Console.WriteLine(MaxElementSum(nums));
    }
}

Python's slicing efficiently models each grouping of elements, iterating through feasibly perfect squares to determine maximal summation.

Complexity

The algorithm runs in O(n√n) time and occupies O(1) additional space.

Try this approach in the editor

Approach 2: Approach 2: Graph Connectivity Concept

Construct a graph with nodes representing indices, and edges exist if their product is a perfect square. Find components (connected subsets) in this graph, and find the sum of the component with maximum node weight (i.e., element value sum).

Python

def dfs(node, visited, nums, component_sum, n):
    visited[node] = True
    component_sum[0] += nums[node]

    for neighbor in range(n):
        if not visited[neighbor] and (node+1) * (neighbor+1) == int((node+1) * (neighbor+1))**2:
            dfs(neighbor, visited, nums, component_sum, n)


def max_element_sum(nums):
    n = len(nums)
    visited = [False] * n
    max_sum = 0

    for i in range(n):
        if not visited[i]:
            component_sum = [0]
            dfs(i, visited, nums, component_sum, n)
            if component_sum[0] > max_sum:
                max_sum = component_sum[0]

    return max_sum

nums = [8, 10, 3, 8, 1, 13, 7, 9, 4]
print(max_element_sum(nums))

Java

import java.util.*;

public class Main {
    private static void dfs(int node, boolean[] visited, int[] nums, int[] componentSum, int n) {
        visited[node] = true;
        componentSum[0] += nums[node];

        for (int neighbor = 0; neighbor < n; neighbor++) {
            if (!visited[neighbor] && Math.floor(Math.sqrt((node + 1) * (neighbor + 1))) == Math.sqrt((node + 1) * (neighbor + 1))) {
                dfs(neighbor, visited, nums, componentSum, n);
            }
        }
    }

    public static int maxElementSum(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int maxSum = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int[] componentSum = new int[]{0};
                dfs(i, visited, nums, componentSum, n);
                if (componentSum[0] > maxSum) {
                    maxSum = componentSum[0];
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
        System.out.println(maxElementSum(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>

void dfs(int node, std::vector<int>& nums, std::vector<bool>& visited, int& componentSum, int n) {
    visited[node] = true;
    componentSum += nums[node];
    for (int neighbor = 0; neighbor < n; ++neighbor) {
        if (!visited[neighbor] && std::floor(std::sqrt((node + 1) * (neighbor + 1))) == std::sqrt((node + 1) * (neighbor + 1))) {
            dfs(neighbor, nums, visited, componentSum, n);
        }
    }
}

int maxElementSum(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<bool> visited(n, false);
    int maxSum = 0;
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            int componentSum = 0;
            dfs(i, const_cast<std::vector<int>&>(nums), visited, componentSum, n);
            if (componentSum > maxSum) {
                maxSum = componentSum;
            }
        }
    }
    return maxSum;
}

int main() {
    std::vector<int> nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
    std::cout << maxElementSum(nums) << std::endl;
    return 0;
}

JavaScript

function dfs(node, nums, visited, componentSum, n) {
    visited[node] = true;
    componentSum[0] += nums[node];

    for (let neighbor = 0; neighbor < n; neighbor++) {
        if (!visited[neighbor] && Math.floor(Math.sqrt((node + 1) * (neighbor + 1))) === Math.sqrt((node + 1) * (neighbor + 1))) {
            dfs(neighbor, nums, visited, componentSum, n);
        }
    }
}

function maxElementSum(nums) {
    const n = nums.length;
    const visited = new Array(n).fill(false);
    let maxSum = 0;

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            let componentSum = [0];
            dfs(i, nums, visited, componentSum, n);
            maxSum = Math.max(maxSum, componentSum[0]);
        }
    }
    return maxSum;
}

const nums = [8, 10, 3, 8, 1, 13, 7, 9, 4];
console.log(maxElementSum(nums));

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>

int nums[10000];
bool visited[10000];

void dfs(int node, int n, int* component_sum) {
    visited[node] = true;
    *component_sum += nums[node];
    for (int neighbor = 1; neighbor <= n; ++neighbor) {
        if (!visited[neighbor-1] && (int)sqrt(node * neighbor) * (int)sqrt(node * neighbor) == node * neighbor) {
            dfs(neighbor-1, n, component_sum);
        }
    }
}

int maxElementSum(int* arr, int n) {
    memcpy(nums, arr, n * sizeof(int));
    memset(visited, 0, sizeof(visited));
    int maxSum = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i-1]) {
            int component_sum = 0;
            dfs(i-1, n, &component_sum);
            if (component_sum > maxSum) {
                maxSum = component_sum;
            }
        }
    }
    return maxSum;
}

int main() {
    int arr[] = {8, 10, 3, 8, 1, 13, 7, 9, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", maxElementSum(arr, n));
    return 0;
}

using System;

class MainClass {
    static void DFS(int node, bool[] visited, int[] nums, ref int componentSum, int n) {
        visited[node] = true;
        componentSum += nums[node];

        for (int neighbor = 0; neighbor < n; neighbor++) {
            if (!visited[neighbor] && Math.Floor(Math.Sqrt((node + 1) * (neighbor + 1))) == Math.Sqrt((node + 1) * (neighbor + 1))) {
                DFS(neighbor, visited, nums, ref componentSum, n);
            }
        }
    }

    static int MaxElementSum(int[] nums) {
        int n = nums.Length;
        bool[] visited = new bool[n];
        int maxSum = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int componentSum = 0;
                DFS(i, visited, nums, ref componentSum, n);
                if (componentSum > maxSum) {
                    maxSum = componentSum;
                }
            }
        }
        return maxSum;
    }

    public static void Main(string[] args) {
        int[] nums = {8, 10, 3, 8, 1, 13, 7, 9, 4};
        Console.WriteLine(MaxElementSum(nums));
    }
}

Uses recursive DFS to explore graph connectivity, building connected components of maximum summed value when node products yield squares.

Complexity

Time complexity is O(n^2) and space complexity is O(n).

Try this approach in the editor

Approach 3: Enumeration

We note that if a number can be expressed in the form of k times j^2, then all numbers of this form have the same k.

Therefore, we can enumerate k in the range [1,..n], and then start enumerating j from 1, each time adding the value of nums[k times j^2 - 1] to t, until k times j^2 > n. At this point, update the answer to ans = max(ans, t).

Finally, return the answer ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function maximumSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    for (let k = 1; k <= n; ++k) {
        let t = 0;
        for (let j = 1; k * j * j <= n; ++j) {
            t += nums[k * j * j - 1];
        }
        ans = Math.max(ans, t);
    }
    return ans;
}

func maximumSum(nums []int) (ans int64) {
	n := len(nums)
	for k := 1; k <= n; k++ {
		var t int64
		for j := 1; k*j*j <= n; j++ {
			t += int64(nums[k*j*j-1])
		}
		ans = max(ans, t)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Factorization-Based Grouping	The algorithm runs in O(n√n) time and occupies O(1) additional space.
Approach 2: Graph Connectivity Concept	Time complexity is O(n^2) and space complexity is O(n).
Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Factorization-Based Grouping	O(n log n)	O(n)	Best general solution. Uses square-free kernel grouping to aggregate sums efficiently.
Graph Connectivity via Square Multipliers	O(n sqrt(n))	O(n)	Useful for conceptual understanding of the index relationships or when modeling the problem as components.

Frequently asked questions

Is Maximum Element-Sum of a Complete Subset of Indices easy or hard?

Maximum Element-Sum of a Complete Subset of Indices is classified as Hard on LeetCode. The challenge comes from recognizing the number theory property that converts the pairwise perfect-square condition into grouping by square-free index factors.

Maximum Element-Sum of a Complete Subset of Indices Python/Java solution

Python and Java implementations typically compute the square-free kernel for each index, store cumulative sums in a hash map, and track the maximum group sum. The logic is identical across languages and runs in O(n log n) time with O(n) space.

How to solve Maximum Element-Sum of a Complete Subset of Indices in O(n)?

A near-linear solution is possible by precomputing smallest prime factors using a sieve and deriving the square-free kernel of each index in constant amortized time. Group indices by this kernel and accumulate sums, effectively achieving O(n) to O(n log log n) preprocessing with O(n) traversal.

What is the best approach for Maximum Element-Sum of a Complete Subset of Indices?

The optimal approach groups indices by their square-free kernel using prime factorization. If two indices have the same square-free representation, their product is guaranteed to be a perfect square. Summing array values for each group and returning the maximum produces the result in O(n log n) time and O(n) space.

Is Maximum Element-Sum of a Complete Subset of Indices asked at Google/Amazon/Meta?

This problem is categorized as Hard and involves number theory and mathematical transformations, patterns commonly seen in interviews at companies like Google, Amazon, and Meta. Variations involving perfect squares, factorization, or index grouping appear in algorithmic interview rounds.

What data structure is used in Maximum Element-Sum of a Complete Subset of Indices?

The main data structure is a hash map that groups indices by their square-free kernel. Additional tools include prime factorization or sieve arrays for number theory preprocessing, along with basic array traversal.

What is the time complexity of Maximum Element-Sum of a Complete Subset of Indices?

The optimal factorization-based grouping runs in O(n log n) time with O(n) space. Each index is reduced to its square-free form using prime factorization or precomputed smallest prime factors, and values are aggregated using a hash map.

Maximum Element-Sum of a Complete Subset of Indices solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Factorization-Based Grouping

Approach 2: Approach 2: Graph Connectivity Concept

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Element-Sum of a Complete Subset of Indices solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Factorization-Based Grouping

Approach 2: Approach 2: Graph Connectivity Concept

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems