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

Power of Heroes

Number: 2784

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums representing the strength of some heroes, we define the power of any non-empty group of heroes as (maximum strength in the group)² multiplied by (minimum strength in the group). The task is to compute the sum of the power of every possible non-empty group of heroes modulo 10⁹ + 7.

Key Insights

  • The brute force approach of enumerating all 2ⁿ - 1 subsets is infeasible for n up to 10⁵.
  • Sorting the array (in non-decreasing order) allows us to treat any valid subset by its first (minimum) and last (maximum) element.
  • For a fixed pair (i, j) with i ≤ j in the sorted array, any subset with minimum element nums[i] and maximum element nums[j] yields a contribution of nums[j]² * nums[i]. The number of such subsets (when i < j) is 2^(j-i-1). For i == j the contribution is simply nums[i]³.
  • By reversing the double summation order and defining a helper cumulative value, we can derive a recurrence relation to aggregate the pair contributions in a single pass.

Space and Time Complexity

Time Complexity: O(n log n) (dominated by sorting) and O(n) for the linear pass.
Space Complexity: O(n) (for storing the sorted array, or O(1) extra space if sorting in-place).

Solution

The solution begins by sorting the array. Every individual hero (a single-element group) contributes its cube (nums[i]³) to the total sum. For groups with more than one element, consider the sorted order: let an element at index j serve as the maximum in the group. All valid minimum elements come from indices i (i < j), and for each such pair (i, j) the number of groups with that fixed minimum and maximum is 2^(j-i-1). Summing these contributions directly would be O(n²), so we define a cumulative variable g, where g(j) represents the weighted sum of candidates for the minimum when index j is the current maximum. With some algebra we derive the recurrence:

  g(1) = nums[0]
  g(j+1) = 2 * g(j) + nums[j]

Then, for each index j (from 1 to n-1), the contribution for the maximum element is: nums[j]² multiplied by g(j). Adding all these pair contributions with the single element contributions (the cubes) gives the final answer modulo 10⁹ + 7.

Code Solutions

mod = 10**9 + 7

def powerOfHeroes(nums):
    # Sort the heroes' strengths in non-decreasing order
    nums.sort()
    n = len(nums)
    
    # Calculate the sum of individual hero contributions (single-element groups)
    single_sum = 0
    for num in nums:
        single_sum = (single_sum + pow(num, 3, mod)) % mod

    pair_sum = 0  # Sum for groups with at least two elements
    # Initialize cumulative weighted sum g with first element
    g = nums[0]
    
    # Iterate over possible maximum elements (index j)
    for j in range(1, n):
        # Every group ending with nums[j] contributes (nums[j]^2 * weighted minimum)
        pair_sum = (pair_sum + (nums[j] * nums[j] % mod) * g) % mod
        # Update g using the recurrence relation: g(j+1) = 2*g(j) + nums[j]
        g = (2 * g + nums[j]) % mod

    # The total power is the sum of single-element contributions and pairs' contributions
    return (single_sum + pair_sum) % mod

# Example usage:
if __name__ == "__main__":
    print(powerOfHeroes([2, 1, 4]))  # Expected output: 141
← Back to All Questions