We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Element-Sum of a Complete Subset of Indices

Number: 3047

Difficulty: Hard

Paid? No

Companies: Purplle

Problem Description

Given a 1-indexed array nums, the goal is to select a "complete subset" of indices such that for every pair of selected indices i and j, the product i * j is a perfect square. Return the sum of the selected elements (from nums) corresponding to a complete subset that has the maximum sum.

A key observation is that if every pair (i, j) in the subset must yield a perfect square when multiplied, then the indices in the subset must share a common property. In fact, by decomposing each index i into i = (square part) * (square-free part), one can show that i * j is a perfect square if and only if the square-free parts of i and j are identical. Therefore, the problem reduces to grouping indices by their square-free parts and summing the corresponding nums values; the answer is the maximum sum over all such groups.

Key Insights

  • Each index i can be represented as i = s² * r, where r is square-free.
  • For any two indices i and j, i * j is a perfect square if and only if their square-free parts are the same.
  • Thus, valid complete subsets correspond exactly to indices that share the same square-free part.
  • The solution is to group indices by their square-free part and choose the group with the maximum element sum.

Space and Time Complexity

Time Complexity: O(n * √n) in worst-case (n <= 10⁴, with each index factorized in O(√i) time). Space Complexity: O(n) for storing the grouping and intermediate results.

Solution

The approach involves:

  1. For each index from 1 to n (remembering that nums is 1-indexed), compute its square-free part. This can be done by checking for each prime factor up to √i and dividing out perfect square factors.
  2. Create a mapping from the square-free part to the cumulative sum of the corresponding nums values.
  3. Return the maximum sum among these groups.

To implement these steps, the code leverages a simple factorization procedure (suitable since n is at most 10⁴) and hash table/dictionary to group the sums.

Code Solutions

# Python solution for Maximum Element-Sum of a Complete Subset of Indices

def maximumElementSum(nums):
    # Helper function to compute square-free part of a number
    def square_free(n):
        factor = 2
        result = 1  # will hold the product of distinct prime factors
        # check potential factors up to sqrt(n)
        while factor * factor <= n:
            if n % factor == 0:
                # If factor divides n, then factor is one of the prime factors.
                count = 0
                while n % factor == 0:
                    count += 1
                    n //= factor
                # Only multiply once if the factor appears (we want the square-free part)
                result *= factor
            factor += 1
        # If there's any prime factor left greater than sqrt(n)
        if n > 1:
            result *= n
        return result

    n = len(nums)
    group_sum = {}  # mapping: square_free(index) -> sum of elements at that index
    # Loop over indices 1-indexed
    for i in range(1, n+1):
        key = square_free(i)
        # Since nums is 0-indexed, we use nums[i-1]
        group_sum[key] = group_sum.get(key, 0) + nums[i-1]
    
    # Return the maximum sum among the groups
    return max(group_sum.values())


# Example usage:
print(maximumElementSum([8,7,3,5,7,2,4,9]))  # Expected output: 16
print(maximumElementSum([8,10,3,8,1,13,7,9,4]))  # Expected output: 20
← Back to All Questions