Watch 9 video solutions for Maximum Element-Sum of a Complete Subset of Indices, a hard level problem involving Array, Math, Number Theory. This walkthrough by Aryan Mittal has 2,026 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1041 <= nums[i] <= 109Problem 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 | 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. |