Back

3047. Maximum Element-Sum of a Complete Subset of Indices

Hard
Array
Math
Number Theory
Solve on LeetCode View Solutions

Description

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 <= 104
  • 1 <= nums[i] <= 109

Hints

Hint 1
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>.
Hint 2
If <code>P(i) = P(j)</code>, <code>nums[i]</code> and <code>nums[j]</code> can be grouped together.
Hint 3
Pick the group with the largest sum.

Similar Questions

Constrained Subsequence Sum
Hard
Maximum Alternating Subsequence Sum
Medium

Statistics

Acceptance
42.8%
Submissions
22,149
Accepted
9,478