2681

2681. Power of Heroes (Hard)

You are given a 0-indexed integer array nums representing the strength of some heroes. The power 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 109 + 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 <= 105
• 1 <= nums[i] <= 109

Related Topics:
Array, Math, Sorting, Prefix Sum

Hints:

• Try something with sorting the array.
• For a pair of array elements nums[i] and nums[j] (i < j), the power would be nums[i]*nums[j]^2 regardless of how many elements in between are included.
• The number of subsets with the above as power will correspond to 2^(j-i-1).
• Try collecting the terms for nums[0], nums[1], …, nums[j-1] when computing the power of heroes ending at index j to get the power in a single pass.

Solution 1.

Assume A=[1,2,3,4], the answer is the sum of the following

// group of numbers ending with 1
1 * 1^2 * 2^0

// group of numbers ending with 2
1 * 2^2 * 2^0
2 * 2^2 * 2^0

// group of numbers ending with 3
1 * 3^2 * 2^1
2 * 3^2 * 2^0
3 * 3^2 * 2^0

// group of numbers ending with 4
1 * 4^2 * 2^2
2 * 4^2 * 2^1
3 * 4^2 * 2^0
4 * 4^2 * 2^0

// OJ: https://leetcode.com/problems/power-of-heroes
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int sumOfPower(vector<int>& A) {
        sort(begin(A), end(A));
        long N = A.size(), mod = 1e9 + 7, sum = 0, ans = 0;
        for (long n : A) {
            ans = (ans + n * n % mod * (sum + n) % mod) % mod;
            sum = (sum * 2 % mod + n);
        }
        return ans;
    }
};