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] <= 109For #2862 Maximum Element-Sum of a Complete Subset of Indices, the key observation comes from number theory. A subset of indices is considered complete when the product of any pair of indices forms a perfect square. This property implies that all indices in such a subset share the same square-free core (the number remaining after removing all square factors).
Instead of checking all subsets, group indices that share the same square-free representation. Another practical way to view this is by iterating a base index i and adding elements located at positions i * j * j, since multiplying by a square preserves the same square-free structure. Accumulate the sum of elements belonging to each valid group and track the maximum.
This approach avoids brute-force subset checks and leverages mathematical structure to reduce the search space. The method runs efficiently for large arrays by iterating square multiples rather than enumerating subsets.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Group indices by square-free base using square multiples | O(n * sqrt(n)) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Define <strong>P(x)</strong> as the product of primes <strong>p</strong> with odd exponents in <strong>x</strong>'s factorization. Examples: For <code>x = 18</code>, factorization <code>2<sup>1</sup> × 3<sup>2</sup></code>, <strong>P(18) = 2</strong>; for <code>x = 45</code>, factorization <code>3<sup>2</sup> × 5<sup>1</sup></code>, <strong>P(45) = 5</strong>; for <code>x = 50</code>, factorization <code>2<sup>1</sup> × 5<sup>2</sup></code>, <strong>P(50) = 2</strong>; for <code>x = 210</code>, factorization <code>2<sup>1</sup> × 3<sup>1</sup> × 5<sup>1</sup> × 7<sup>1</sup></code>, <strong>P(210) = 210</strong>.
If <code>P(i) = P(j)</code>, <code>nums[i]</code> and <code>nums[j]</code> can be grouped together.
Pick the group with the largest sum.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The square-free representation identifies the fundamental factor of a number after removing all perfect square factors. If two indices share the same square-free part, their product becomes a perfect square, which satisfies the condition for a complete subset.
Problems involving number theory patterns, square factors, and grouping techniques appear frequently in high-level coding interviews. While this exact question may not always appear, similar mathematical insight problems are common in FAANG-style interviews.
The optimal approach uses number theory. Indices that belong to a valid subset share the same square-free base, meaning their products form perfect squares. By grouping indices using this property or iterating square multiples, we can compute the maximum element sum efficiently.
The problem can be solved efficiently using simple iteration and arithmetic grouping, so only variables for tracking sums and the maximum value are needed. In some implementations, a hash map can also be used to group sums by square-free keys.