Description Link to heading

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 i₀, i₁, … , iₖ be the indices of the heroes in a group. Then, the power of this group is max(nums[i₀], nums[i₁], ... ,nums[iₖ])² * min(nums[i₀], nums[i₁], ... ,nums[iₖ]).

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

Example 1:

Input: nums = [2,1,4]
Output: 141
Explanation:
1st group: [2] has power = 2² * 2 = 8.
2ⁿd group: [1] has power = 1² * 1 = 1.
3rd group: [4] has power = 4² * 4 = 64.
4th group: [2,1] has power = 2² * 1 = 4.
5th group: [2,4] has power = 4² * 2 = 32.
6th group: [1,4] has power = 4² * 1 = 16.
7th group: [2,1,4] has power = 4² * 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⁵
  • 1 <= nums[i] <= 10⁹

Solution Link to heading

Firstly, when dealing with array-related problems, we should consider whether sorting the array in advance would be beneficial. In this particular problem of selecting subsequences, since the subsequence can be non-contiguous, the order of the elements in the array does not affect the result.

Next, we can adopt the approach of contribution, where we consider the contribution of each element as the maximum value to the final result.

For example, let’s consider the array $[1, 2, 3, 4, 5]$. The contribution of the element $4$ as the maximum value can be calculated as $4^2 \times (1 \times 2^2 + 2 \times 2^1 + 3 \times 2^0) + 4^3$, which we denote as $a_3^2 s_3 + a_3^3$. Similarly, the contribution of the element $5$ as the maximum value is calculated as $5^2 \times (1 \times 2^3 + 2 \times 2^2 + 3 \times 2^1 + 4) + 5^3$, denoted as $a_4^2 s_4 + a_4^3$.

We have the recurrence relation $s_i = 2 \times s_{i - 1} + a_{i - 1}$.

Hence, we can compute the result in constant time $O(1)$, while being mindful of taking modulo to prevent overflow.

Code Link to heading 

class Solution {
  public:
    int sumOfPower(vector<int> &nums) {
        int mod = 1000000007;
        sort(nums.begin(), nums.end());
        long res = 0;
        long s = 0;
        int n = nums.size();
        for (long num : nums) {
            res = (res + ((num * num) % mod) * ((num + s) % mod)) % mod;
            s = (2 * s + num) % mod;
        }
        return res;
    }
};