Maximum Element-Sum of a Complete Subset of Indices
HardPrompt
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] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This is an optimized version of the first approach. It recognizes that calculating the square-free part for each index from scratch is inefficient. By precomputing the square-free parts for all numbers from 1 to n using a sieve, we can reduce the time complexity significantly. The sieve efficiently removes all perfect square factors from each number in nearly linear time. Once the precomputation is done, the problem is solved by grouping and summing the elements, just like in the previous approach, but with a much faster lookup for the square-free parts.
Algorithm
- This approach uses the same fundamental principle of grouping indices by their square-free part.
- To improve efficiency, it avoids re-calculating the square-free part for each index individually.
- Instead, it precomputes the square-free parts for all numbers from
1tonusing a sieve-like algorithm. - The sieve works by iterating through numbers
jand for eachj, removing the perfect square factorj*jfrom all its multiples up ton. - After this
O(n)precomputation, the main logic proceeds as before: iterate through indices, look up the precomputed square-free part, and aggregate sums in a hash map.
Walkthrough
The bottleneck in the previous approach is the repeated calculation within the main loop. We can optimize this by pre-calculating all necessary square-free parts at once.
Algorithm Steps:
- Precomputation with a Sieve:
- Create an integer array
sfof sizen + 1. - Initialize
sf[i] = ifor allifrom1ton. - Iterate with a number
jfrom2up ton. Ifj*j > n, we can stop. - For each
j, letsquare = j * j. - Iterate through all multiples of
squareup ton(i.e.,m = square, 2*square, 3*square, ...). - For each multiple
m, repeatedly dividesf[m]bysquareuntil it's no longer divisible. This effectively removes the perfect square factorj*jfromsf[m].
- Create an integer array
- Grouping and Summation:
- Initialize a
HashMap<Integer, Long>calledgroupSums. - Iterate with an index
ifrom1ton. - The square-free part of
iis now a simple lookup:core = sf[i]. - Add
nums[i-1]to the sum for the groupcorein thegroupSumsmap.
- Initialize a
- Find Maximum:
- Find and return the maximum value present in the
groupSumsmap.
- Find and return the maximum value present in the
This precomputation step changes the overall time complexity from O(n * sqrt(n)) to nearly O(n).
import java.util.HashMap;import java.util.Map; class Solution { public long maximumSum(int[] nums) { int n = nums.length; // Step 1: Precompute square-free parts for 1 to n using a sieve int[] sf = new int[n + 1]; for (int i = 1; i <= n; i++) { sf[i] = i; } for (int j = 2; j * j <= n; j++) { int square = j * j; for (int m = square; m <= n; m += square) { while (sf[m] % square == 0) { sf[m] /= square; } } } // Step 2: Group sums based on the precomputed square-free parts Map<Integer, Long> groupSums = new HashMap<>(); for (int i = 1; i <= n; i++) { int core = sf[i]; // O(1) lookup long currentVal = nums[i - 1]; groupSums.put(core, groupSums.getOrDefault(core, 0L) + currentVal); } // Step 3: Find the maximum sum among all groups long maxSum = 0; for (long sum : groupSums.values()) { maxSum = Math.max(maxSum, sum); } return maxSum; }}Complexity
Time
O(n log log n) - The sieve precomputation step runs in `O(n log log n)` or `O(n)` time, which is much faster than `O(n * sqrt(n))`. The summation part runs in `O(n)`. Therefore, the total time complexity is dominated by the sieve and is effectively linear.
Space
O(n) - This approach requires `O(n)` space for the `sf` array used in the sieve, plus `O(n)` space for the hash map in the worst case.
Trade-offs
Pros
Highly efficient with a nearly linear time complexity.
Optimal solution for the given constraints.
Cons
Requires additional
O(n)space for the sieve array.The sieve logic, while efficient, can be slightly more complex to understand and implement compared to the direct calculation.
This approach solves the problem by identifying the fundamental property of the complete subset: all indices in such a subset must share the same 'square-free part'. It iterates through each index, calculates this property, and groups the corresponding nums values. A hash map is used to keep track of the sum of elements for each group. The final answer is the largest sum found among all groups.
Algorithm
- The core idea is that for any two indices
iandjin a valid subset, the producti * jmust be a perfect square. - This condition holds if and only if
iandjhave the same square-free part. The square-free part of a number is the number itself divided by the largest perfect square that divides it (e.g., for12 = 4 * 3, the square-free part is3). - This observation allows us to partition all indices from
1toninto groups based on their square-free part. - To get the maximum sum, we should find the sum of elements for each group and then take the maximum among all these group sums.
- This approach iterates through each index
ifrom1ton, calculates its square-free part on the fly, and uses a hash map to maintain the sum for each group.
Walkthrough
The problem requires finding a subset of indices where the product of any pair is a perfect square. This property is equivalent to all indices in the subset having the same square-free core. For example, sf(8) = 2 (since 8 = 4 * 2) and sf(2) = 2. Thus, indices 2 and 8 can be in the same set, as 2 * 8 = 16 is a perfect square.
This method directly implements this logic:
- Initialize a
HashMap<Integer, Long>calledgroupSumsto map a square-free core to the sum ofnumsvalues for all indices sharing that core. - Iterate with an index
ifrom1ton(wherenis the length ofnums). - For each
i, calculate its square-free part. This is done in a helper function,getSquareFreePart(i), which works by trial division. It iterates fromd = 2up tosqrt(i)and for eachd, it dividesibyd*das many times as possible. - Retrieve the value
nums[i-1](usingi-1for 0-based array access). - Add this value to the running sum for the calculated square-free part in the
groupSumsmap. - After the loop finishes, iterate through the values of the
groupSumsmap to find the maximum sum. - Return this maximum sum.
import java.util.HashMap;import java.util.Map; class Solution { /** * Calculates the square-free part of a number n. * A number's square-free part is what remains after dividing out all perfect square factors. * Example: sf(72) -> 72 = 36 * 2 -> sf is 2. */ private int getSquareFreePart(int n) { int num = n; for (int i = 2; i * i <= num; i++) { // If i*i is a factor, divide it out completely. while (num % (i * i) == 0) { num /= (i * i); } } return num; } public long maximumSum(int[] nums) { int n = nums.length; Map<Integer, Long> groupSums = new HashMap<>(); // Iterate through 1-based indices for (int i = 1; i <= n; i++) { int core = getSquareFreePart(i); long currentVal = nums[i - 1]; groupSums.put(core, groupSums.getOrDefault(core, 0L) + currentVal); } long maxSum = 0; for (long sum : groupSums.values()) { maxSum = Math.max(maxSum, sum); } return maxSum; }}Complexity
Time
O(n * sqrt(n)) - The main loop runs `n` times. Inside the loop, the `getSquareFreePart(i)` function takes roughly `O(sqrt(i))` time. The total time complexity is the sum of `sqrt(i)` for `i` from 1 to `n`, which is approximated by the integral of `sqrt(x)`, resulting in `O(n^(3/2))` or `O(n * sqrt(n))`. For `n=10^4`, this is about `10^6` operations, which is acceptable.
Space
O(n) - In the worst-case scenario, every index from 1 to n could have a unique square-free part, requiring the hash map to store up to `n` entries.
Trade-offs
Pros
The logic is straightforward and directly follows from the mathematical property.
It's relatively easy to implement without complex data structures.
Cons
The time complexity of
O(n * sqrt(n))can be slow, although it passes for the given constraints (n <= 10^4).It performs redundant computations, as the square-free part of a number is calculated independently each time.
Solutions
Solution
class Solution {public long maximumSum(List<Integer> nums) { long ans = 0; int n = nums.size(); boolean[] used = new boolean[n + 1]; int bound = (int)Math.floor(Math.sqrt(n)); int[] squares = new int[bound + 1]; for (int i = 1; i <= bound + 1; i++) { squares[i - 1] = i * i; } for (int i = 1; i <= n; i++) { long res = 0; int idx = 0; int curr = i * squares[idx]; while (curr <= n) { res += nums.get(curr - 1); curr = i * squares[++idx]; } ans = Math.max(ans, res); } return ans; }}class Solution {public: long long maximumSum(vector<int> &nums) { long long ans = 0; int n = nums.size(); for (int k = 1; k <= n; ++k) { long long t = 0; for (int j = 1; k * j * j <= n; ++j) { t += nums[k * j * j - 1]; } ans = max(ans, t); } return ans; }};class Solution: def maximumSum(self, nums: List[int]) -> int: n = len(nums) ans = 0 for k in range(1, n + 1): t = 0 j = 1 while k * j * j <= n: t += nums[k * j * j - 1] j += 1 ans = max(ans, t) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.