Leetcode # 2862. Maximum Element-Sum of a Complete Subset of Indices

Problem

https://leetcode.com/contest/weekly-contest-363/problems/maximum-element-sum-of-a-complete-subset-of-indices/

1. complete(set_of_numbers) ← True, if ∀ x, y ∈ set_of_numbers, ∃ z ∈ ℕ s.t. x * y == z ** 2
   x can equal to y
   
2. subset_of_the_indices := [index₀, index₁, index₂, …], index_i ∈ ℕ (1-indexed)
3. element_sum(subset_of_the_indices) := sum(nums[index – 1] for index in subset_of_the_indices)
4. return max(element_sum(s) for s in all_subsets if complete(s))

Testcases

First Solution: Sieve of Eratosthenes

n := len(nums)

Time Complexity: O(n)
Space Complexity: more than O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumSum(self, nums: List[int]) -> int:
    n = len(nums)
    prime_factors = [Counter() for i in range(n + 1)]
    subsets_sum, subset_i = defaultdict(int), [0] * (n + 1)
    result = max(nums)
    for i in range(2, n + 1):
      if not prime_factors[i]:
        for j in range(i, n + 1, i):
          _j = j
          while _j % i == 0:
            prime_factors[j][i] += 1
            _j //= i
      c = prod(f for f in prime_factors[i] if prime_factors[i][f] % 2 != 0)
      if c < i:
        if subset_i[i] == subset_i[c] == 0:
          subset_i[c] = c
          subsets_sum[subset_i[c]] += nums[c - 1]
        subset_i[i] = subset_i[c]
        subsets_sum[subset_i[c]] += nums[i - 1]
        result = max(result, subsets_sum[subset_i[c]])
    
    return result

More Simple Solution

x * y * y <= len(n) ⇒ y <= sqrt(n / x)

Time Complexity: O(n * log(n))
Space Complexity: more than O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumSum(self, nums: List[int]) -> int:
    return max(sum(nums[x * y * y - 1] for y in range(1, isqrt(len(nums) // x) + 1)) for x in range(1, len(nums) + 1))

Last Updated on 2023/09/19 by A1go