2862. Maximum Element-Sum of a Complete Subset of Indices LeetCode Solution
In this guide, you will get 2862. Maximum Element-Sum of a Complete Subset of Indices LeetCode Solution with the best time and space complexity. The solution to Maximum Element-Sum of a Complete Subset of Indices problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Element-Sum of a Complete Subset of Indices
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2862. Maximum Element-Sum of a Complete Subset of Indices LeetCode Solution in C++
class Solution {
public:
long long maximumSum(vector<int>& nums) {
long ans = 0;
unordered_map<int, long> oddPowerToSum;
for (int i = 0; i < nums.size(); ++i) {
const int oddPower = divideSquares(i + 1);
ans = max(ans, oddPowerToSum[oddPower] += nums[i]);
}
return ans;
}
private:
int divideSquares(int val) {
for (int num = 2; num * num <= val; ++num)
while (val % (num * num) == 0)
val /= num * num;
return val;
}
}; /* code provided by PROGIEZ */
2862. Maximum Element-Sum of a Complete Subset of Indices LeetCode Solution in Java
class Solution {
public long maximumSum(List<Integer> nums) {
long ans = 0;
HashMap<Integer, Long> oddPowerToSum = new HashMap<>();
for (int i = 0; i < nums.size(); ++i) {
final int oddPower = divideSquares(i + 1);
ans = Math.max(ans, oddPowerToSum.merge(oddPower, (long) nums.get(i), Long::sum));
}
return ans;
}
private int divideSquares(int val) {
for (int num = 2; num * num <= val; ++num)
while (val % (num * num) == 0)
val /= num * num;
return val;
}
} // code provided by PROGIEZ
2862. Maximum Element-Sum of a Complete Subset of Indices LeetCode Solution in Python
class Solution:
def maximumSum(self, nums: list[int]) -> int:
ans = 0
oddPowerToSum = collections.Counter()
def divideSquares(val: int) -> int:
for num in range(2, val + 1):
while val % (num * num) == 0:
val //= (num * num)
return val
for i, num in enumerate(nums):
oddPower = divideSquares(i + 1)
oddPowerToSum[oddPower] += num
ans = max(ans, oddPowerToSum[oddPower])
return ans # code by PROGIEZ
