LeetCode Problem 2862

Difficulty: 🔴 Hard
Topics: Array, Math, Number Theory

Solution

LeetCode 2862 - Maximum Element-Sum of a Complete Subset of Indices

Problem Understanding

The array nums is 1-indexed, meaning the first element corresponds to index 1, the second element corresponds to index 2, and so on.

We want to select a subset of indices such that for every pair of selected indices i and j, the product i * j is a perfect square.

Among all subsets that satisfy this condition, we need to find the one whose corresponding elements have the largest possible sum.

The key challenge is understanding what kinds of index sets satisfy the condition that every pairwise product is a perfect square.

The input size is up to n = 10^4, which is large enough that checking all possible subsets is completely infeasible. Since each value can be as large as 10^9, the solution must focus on the structure of the indices rather than the values themselves.

Several edge cases are worth noting immediately:

• The optimal subset may contain only a single index.
• Multiple indices can belong to the same valid group.
• The array values are always positive, so adding more valid indices from the same group can only increase the sum.
• Since n is only 10^4, we can afford preprocessing information about every index.

Approaches

Brute Force

A brute-force solution would attempt to generate subsets of indices and verify whether every pair inside the subset satisfies the perfect-square condition.

For a candidate subset of size k, we would need to check all O(k²) pairs. Since there are 2^n possible subsets, the overall complexity becomes astronomical.

Even if we tried to build subsets incrementally, the search space remains exponential and is completely impossible for n = 10^4.

The brute-force method is correct because it explicitly examines every valid subset and returns the maximum sum, but it is far too slow.

Key Insight

The important observation comes from prime factorization.

Every positive integer can be written as:

$$i = s \times t^2$$

where:

• s is square-free, meaning no prime factor appears more than once.
• t^2 is a perfect square.

The value s is called the square-free kernel of i.

Consider two indices:

$$i = s_1 a^2$$

$$j = s_2 b^2$$

Their product is:

$$i \cdot j = s_1 s_2 (ab)^2$$

For this product to be a perfect square, every prime exponent must be even. Since s₁ and s₂ are square-free, this happens only when:

$$s_1 = s_2$$

Therefore:

• Two indices have a perfect-square product if and only if they have the same square-free kernel.
• Any set of indices sharing the same square-free kernel automatically satisfies the pairwise condition.

This transforms the problem into grouping indices by their square-free kernel and summing the corresponding values.

The answer is simply the maximum group sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2ⁿ · n²)	O(n)	Enumerates all subsets and checks pairwise products
Optimal	O(n√n)	O(n)	Group indices by square-free kernel

Algorithm Walkthrough

Optimal Algorithm

1. Create a hash map that will store the sum of elements for each square-free kernel.
2. Iterate through all indices from 1 to n.
3. For each index, compute its square-free kernel.
4. To compute the kernel, repeatedly remove all square factors. For every integer d such that d² ≤ index, divide the index by d² as many times as possible.
5. The remaining value is the square-free kernel.
6. Add nums[index - 1] to the hash map entry corresponding to this kernel.
7. After processing all indices, iterate through the hash map values.
8. Return the largest group sum.

Why it works

Every positive integer can be uniquely decomposed into a square-free part and a square part. Two indices produce a perfect-square product exactly when their square-free parts are equal. Therefore every valid complete subset must lie entirely within a single square-free-kernel group.

Since all numbers in nums are positive, taking all indices from a group always gives a sum at least as large as taking only some of them. Thus the optimal complete subset is exactly the group with the largest total sum.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        group_sum = defaultdict(int)
        n = len(nums)

        for index in range(1, n + 1):
            kernel = index

            d = 2
            while d * d <= kernel:
                square = d * d
                while kernel % square == 0:
                    kernel //= square
                d += 1

            group_sum[kernel] += nums[index - 1]

        return max(group_sum.values())

Implementation Explanation

The hash map group_sum stores the total contribution of every square-free-kernel group.

For each 1-indexed position, we start with kernel = index. We then remove every square factor. For example:

• 12 = 3 × 2², so its kernel becomes 3.
• 18 = 2 × 3², so its kernel becomes 2.
• 36 = 2² × 3², so its kernel becomes 1.

After computing the kernel, we add the corresponding array value into that group's running total.

At the end, every valid complete subset corresponds exactly to one group, so the largest group sum is the answer.

Go Solution

func maximumSum(nums []int) int64 {
	n := len(nums)
	groupSum := make(map[int]int64)

	for index := 1; index <= n; index++ {
		kernel := index

		for d := 2; d*d <= kernel; d++ {
			square := d * d
			for kernel%square == 0 {
				kernel /= square
			}
		}

		groupSum[kernel] += int64(nums[index-1])
	}

	var ans int64
	for _, sum := range groupSum {
		if sum > ans {
			ans = sum
		}
	}

	return ans
}

Go-Specific Notes

The official Go signature returns int64, so all accumulated sums are stored as int64.

The map type is map[int]int64, where the key is the square-free kernel and the value is the total sum for that group.

Unlike Python, Go requires explicit conversion from int to int64 when adding array values.

Worked Examples

Example 1

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

Index	Kernel	Value	Group Sum After Update
1	1	8	kernel 1 → 8
2	2	7	kernel 2 → 7
3	3	3	kernel 3 → 3
4	1	5	kernel 1 → 13
5	5	7	kernel 5 → 7
6	6	2	kernel 6 → 2
7	7	4	kernel 7 → 4
8	2	9	kernel 2 → 16

Final groups:

Kernel	Sum
1	13
2	16
3	3
5	7
6	2
7	4

Maximum sum = 16

Example 2

nums = [8,10,3,8,1,13,7,9,4]

Index	Kernel	Value
1	1	8
2	2	10
3	3	3
4	1	8
5	5	1
6	6	13
7	7	7
8	2	9
9	1	4

Group totals:

Kernel	Sum
1	20
2	19
3	3
5	1
6	13
7	7

Maximum sum = 20

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n√n)	Each index computes its square-free kernel by checking divisors up to √index
Space	O(n)	Hash map storing kernel groups

The outer loop processes all n indices. For an index i, computing the kernel requires testing divisors up to √i. Summing over all indices yields O(n√n) time. With n ≤ 10⁴, this is easily fast enough. The hash map can contain at most n distinct kernels, giving O(n) space usage.

Test Cases

sol = Solution()

assert sol.maximumSum([8,7,3,5,7,2,4,9]) == 16      # example 1
assert sol.maximumSum([8,10,3,8,1,13,7,9,4]) == 20 # example 2

assert sol.maximumSum([5]) == 5                     # single element

assert sol.maximumSum([1,2,3,4]) == 5              # kernel 1 group: indices 1 and 4

assert sol.maximumSum([10,20]) == 20               # best single index

assert sol.maximumSum([1,1,1,1,1,1,1,1,1]) == 3    # indices 1,4,9 share kernel 1

assert sol.maximumSum([1000000000] * 9) == 3000000000  # large values

assert sol.maximumSum([3,1,4,1,5,9,2,6,5,3]) == 10 # mixed kernels

assert sol.maximumSum([7,7,7,7]) == 14             # kernel 1 group gives 7+7

assert sol.maximumSum([1,2,3,4,5,6,7,8,9,10]) == 14 # larger kernel-1 group

Test Summary

Test	Why
[8,7,3,5,7,2,4,9]	Official example 1
[8,10,3,8,1,13,7,9,4]	Official example 2
[5]	Minimum array size
[1,2,3,4]	Tests perfect-square index grouping
[10,20]	Best answer is a single index
Nine ones	Multiple indices sharing kernel 1
Large values	Verifies large sums
Mixed values	General correctness
Four sevens	Multiple equal values
Length ten increasing	Broader grouping behavior

Edge Cases

Single Element Array

When n = 1, the only possible subset contains index 1. A buggy implementation might assume at least two indices are needed to form a complete subset. Since a singleton set vacuously satisfies the pairwise condition, the answer is simply the lone element. The algorithm handles this naturally because kernel 1 receives that value and becomes the maximum group.

Indices That Are Perfect Squares

Indices such as 1, 4, 9, 16, and 25 all have square-free kernel 1. It is easy to overlook that these indices can all be grouped together. The kernel computation repeatedly removes square factors, reducing each of these indices to 1, ensuring they are correctly placed into the same group.

Very Large Array Values

Each nums[i] can be as large as 10^9. A group may contain many indices, causing sums larger than a 32-bit integer can hold. The Go implementation uses int64 for all accumulated sums, preventing overflow. Python integers automatically grow to arbitrary precision, so no special handling is required.

Groups Containing Only One Index

Some kernels may appear only once among the indices from 1 to n. These still represent valid complete subsets because a single element has no pairwise constraints to violate. The algorithm treats every kernel group uniformly, including groups of size one, ensuring the maximum answer is found even when the optimal subset contains a single index.