Skip to main content

2681 - Power of Heroes (Hard)

https://leetcode.com/problems/power-of-heroes/

Problem Statement​

You are given a 0-indexed integer array nums representing the strength of some heroes. Thepower of a group of heroes is defined as follows:

  • Let i0, i1, ... ,ik be the indices of the heroes in a group. Then, the power of this group is max(nums[i0], nums[i1], ... ,nums[ik])2 * min(nums[i0], nums[i1], ... ,nums[ik]).

Return the sum of the power of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 1e9 + 7.

Example 1:

Input: nums = [2,1,4]
Output: 141
Explanation: 
1st group: [2] has power = 22 * 2 = 8.
2nd group: [1] has power = 12 * 1 = 1. 
3rd group: [4] has power = 42 * 4 = 64. 
4th group: [2,1] has power = 22 * 1 = 4. 
5th group: [2,4] has power = 42 * 2 = 32. 
6th group: [1,4] has power = 42 * 1 = 16. 
7th group: [2,1,4] has power = 42 * 1 = 16. 
The sum of powers of all groups is 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141.

Example 2:

Input: nums = [1,1,1]
Output: 7
Explanation: A total of 7 groups are possible, and the power of each group will be 1. Therefore, the sum of the powers of all groups is 7.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Approach 1: Math​

Written by @wingkwong
class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        M = 10 ** 9 + 7
        # sort the input so that we can easily find the min and max
        # besides, sorting won't affect the result since original position doesn't matter
        nums.sort()
        res, s = 0, 0
        for x in nums:
            # if we just include one element [x], 
            # it is easy to see it contributes x * x * x
            # if we include a pair [x, y] where x < y, 
            # it contributes x * y * y 
            # if we include some numbers between x and y, i.e. [x, a, b, c, y] where x < a, b, c < y
            # the power is also x * y * y 
            # the number of subsets will be 2 ^ (j - i + 1)
            # e.g. [x, a, y], [x, a, b, y], [x, a, b, c, y], [x, b, y], [x, b, c] ...
            # hence, for each pair, the power will be x * y * y * 2 ^ (j - i + 1)
            # combining above two cases, for the index j, we got
            # (nums[j] * nums[j] * nums[j]) + (nums[j] * nums[j]) * \sum_{i = 0} ^ {j - 1} (nums[j] * 2 ^ (j - i + 1))
            # so how to calculate \sum_{i = 0} ^ {j - 1} (nums[j] * 2 ^ (j - i + 1)) in a linear time?
            # let F(i) = \sum_{i = 0} ^ {j - 1} (nums[j] * 2 ^ (j - i + 1))
            # rewrite the above formula, then we will see that F(i + 1) would be 2 * F(i) + nums[i]
			# if you have no idea on above mathematic explanation, 
			# try some cases and you will see the pattern
			# nums = [1, 2, 3, 4]
            # 1 * 1 * ((0) + 1)
            # 2 * 2 * ((1) * 2 ^ 0 + 2)
            # 3 * 3 * ((1 * 2 ^ 1 + 2) * 2 ^ 0 + 3)
            # 4 * 4 * ((1 * 2 ^ 2 + 2 * 2 ^ 1 + 3) * 2 ^ 0 + 4)
			# ...
			# x * x * (prev_s * 2 + x)
            res += (x + s) * (x * x) 
            res %= M
            s = (s * 2 + x) % M
        return res