# Power of Heroes
**Difficulty:** HARD
[External](https://leetcode.com/problems/power-of-heroes)
Canonical: https://scaleengineer.com/dsa/problems/power-of-heroes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force by Generating All Subsets
The most straightforward way to solve the problem is to generate every possible non-empty group (subset) of heroes, calculate the power for each group, and sum them up. This can be achieved by iterating through all `2^n - 1` non-empty subsets.
**Time:** O(n * 2^n)

There are `2^n` possible subsets. For each subset, we iterate through its elements to find the minimum and maximum, which takes `O(k)` time where `k` is the subset size (up to `n`). This results in an overall time complexity of `O(n * 2^n)`. · **Space:** O(n)

The space complexity is determined by the depth of the recursion stack, which is `O(n)`, and the space required to store the `currentSubset`, which can also be up to `O(n)`.
**Pros:** Conceptually simple and easy to understand.; Correct for small input sizes.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the constraints specified in the problem.
### Explanation
This approach uses recursion with backtracking to explore all possible combinations of heroes. We define a helper function that builds subsets element by element. For each element in the input array `nums`, we decide whether to include it in the current subset or not. This creates two branches at each step, leading to `2^n` total subsets. Once a complete subset is formed (i.e., we've made a decision for every hero), we check if it's non-empty. If it is, we iterate through the subset to find its minimum and maximum strength values. We then compute its power using the formula `max_strength^2 * min_strength` and add it to a running total. All additions are performed modulo `10^9 + 7` to prevent overflow.

```java
class Solution {
    long totalPower = 0;
    int MOD = 1_000_000_007;

    public int sumOfPower(int[] nums) {
        List<Integer> currentSubset = new ArrayList<>();
        generateSubsets(nums, 0, currentSubset);
        return (int) totalPower;
    }

    private void generateSubsets(int[] nums, int index, List<Integer> currentSubset) {
        if (index == nums.length) {
            if (!currentSubset.isEmpty()) {
                long minVal = Long.MAX_VALUE;
                long maxVal = Long.MIN_VALUE;
                for (int num : currentSubset) {
                    minVal = Math.min(minVal, num);
                    maxVal = Math.max(maxVal, num);
                }
                long maxSq = (maxVal * maxVal) % MOD;
                long power = (maxSq * minVal) % MOD;
                totalPower = (totalPower + power) % MOD;
            }
            return;
        }

        // Decision 1: Exclude nums[index]
        generateSubsets(nums, index + 1, currentSubset);

        // Decision 2: Include nums[index]
        currentSubset.add(nums[index]);
        generateSubsets(nums, index + 1, currentSubset);
        currentSubset.remove(currentSubset.size() - 1); // Backtrack
    }
}
```
### Algorithm
*   Initialize a global variable `totalPower` to 0.
*   Define a recursive function, say `generateSubsets(index, currentSubset)`, to generate all subsets.
*   The function takes the current `index` in the `nums` array and the `currentSubset` being built.
*   **Base Case:** When `index` reaches the end of the array, check if `currentSubset` is non-empty.
    *   If it is, find its minimum and maximum elements.
    *   Calculate the power: `power = (max^2 * min) % MOD`.
    *   Add this `power` to `totalPower`.
*   **Recursive Step:** For each element `nums[index]`, make two recursive calls:
    1.  One call that excludes `nums[index]` from the subset: `generateSubsets(index + 1, currentSubset)`.
    2.  One call that includes `nums[index]` in the subset: add `nums[index]` to `currentSubset`, call `generateSubsets(index + 1, currentSubset)`, and then remove `nums[index]` (backtracking).
*   Start the process by calling `generateSubsets(0, new ArrayList<>())`.
*   Return `totalPower`.

## Sorting and Nested Loops
A significant improvement over the brute-force approach is to first sort the array. After sorting, we can iterate through each element `nums[i]` and consider it as the maximum element of a subset. Then, for each such `nums[i]`, we can iterate through all elements `nums[j]` with `j <= i` and consider them as the minimum. By fixing the minimum and maximum, we can count how many subsets satisfy these conditions and calculate their combined power.
**Time:** O(n^2)

Sorting the array takes `O(n log n)`. The main work is done in the nested loops. The outer loop runs `n` times, and the inner loop runs `i+1` times, leading to a total of `1 + 2 + ... + n = O(n^2)` iterations. · **Space:** O(log n) or O(n)

This depends on the implementation of the sorting algorithm. If an in-place sort like Heapsort is used, it's `O(log n)`. If Mergesort is used, it's `O(n)`. The algorithm itself uses constant extra space.
**Pros:** Much more efficient than the brute-force approach.; The logic is based on a clear combinatorial argument of fixing min and max elements.
**Cons:** The `O(n^2)` complexity is too slow for the given constraints (`n <= 10^5`) and will time out.
### Explanation
By sorting the array `nums`, we can systematically determine the contribution of each element. We iterate through the sorted array with an index `i`, fixing `nums[i]` as the maximum value in a group of subsets. Then, for each `i`, we iterate with an index `j` from `0` to `i`, fixing `nums[j]` as the minimum value.

When `nums[i]` is the max and `nums[j]` is the min:
1.  If `j == i`, the subset can only be `{nums[i]}`. Its power is `nums[i]^2 * nums[i] = nums[i]^3`.
2.  If `j < i`, the subset must contain `nums[i]` and `nums[j]`. The other elements of the subset must be chosen from the elements between `nums[j]` and `nums[i]` in the sorted array, i.e., from `{nums[j+1], ..., nums[i-1]}`. There are `i - j - 1` such elements, and any subset of them can be included. This gives `2^(i-j-1)` possible subsets. Each of these subsets has a power of `nums[i]^2 * nums[j]`. 

Summing these contributions over all possible pairs of `i` and `j` gives the final answer.

```java
import java.util.Arrays;

class Solution {
    public int sumOfPower(int[] nums) {
        int n = nums.length;
        long MOD = 1_000_000_007;
        Arrays.sort(nums);

        long totalPower = 0;

        // Precomputing powers of 2 is not strictly necessary but can be cleaner.
        // Here we calculate it on the fly for simplicity.

        for (int i = 0; i < n; i++) {
            long maxVal = nums[i];
            long maxValSq = (maxVal * maxVal) % MOD;

            for (int j = 0; j <= i; j++) {
                long minVal = nums[j];
                long contribution;
                if (i == j) {
                    contribution = (maxValSq * minVal) % MOD;
                } else {
                    long numIntermediate = i - j - 1;
                    long numSubsets = 1;
                    if (numIntermediate >= 0) {
                       // Simple power calculation
                       numSubsets = power(2, numIntermediate, MOD);
                    }
                    long term = (maxValSq * minVal) % MOD;
                    contribution = (term * numSubsets) % MOD;
                }
                totalPower = (totalPower + contribution) % MOD;
            }
        }
        return (int) totalPower;
    }

    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
*   Sort the input array `nums` in non-decreasing order.
*   Initialize `totalPower = 0`.
*   Optionally, precompute powers of 2 modulo `10^9 + 7` and store them in an array for `O(1)` lookup.
*   Use a nested loop structure:
    *   The outer loop iterates from `i = 0` to `n-1`. `nums[i]` is treated as the maximum element of a set of subsets.
    *   The inner loop iterates from `j = 0` to `i`. `nums[j]` is treated as the minimum element.
*   Inside the loops, calculate the contribution for the pair `(min=nums[j], max=nums[i])`:
    *   If `j == i`, the only subset is `{nums[i]}`. The power is `nums[i]^3`. Add this to `totalPower`.
    *   If `j < i`, the subset must contain `nums[i]` and `nums[j]`. Other elements must be chosen from `{nums[j+1], ..., nums[i-1]}`. There are `i-j-1` such elements, so there are `2^(i-j-1)` ways to form the rest of the subset.
    *   The contribution is `(nums[i]^2 * nums[j]) * 2^(i-j-1)`. Add this to `totalPower`.
*   Ensure all intermediate calculations are done modulo `10^9 + 7`.
*   Return `totalPower`.

## Sorting and Dynamic Programming
The most efficient approach builds upon the sorted array idea but optimizes the calculation using dynamic programming. The `O(n^2)` approach involves a nested sum that can be computed more efficiently. By identifying a recurrence relation for this inner sum, we can reduce the complexity to a single pass over the sorted array.
**Time:** O(n log n)

Sorting the array takes `O(n log n)`. The subsequent single pass through the array to calculate the total power takes `O(n)` time. Therefore, the overall time complexity is dominated by the sort. · **Space:** O(log n) or O(n)

The space is dominated by the sorting algorithm's requirements. The DP approach itself only uses a few variables, which is `O(1)` auxiliary space.
**Pros:** Highly efficient with a linearithmic time complexity.; Passes all test cases within the given constraints.; Uses constant extra space (excluding the space for sorting).
**Cons:** The derivation of the recurrence relation is not immediately obvious and requires careful mathematical formulation.
### Explanation
After sorting `nums`, we can express the total power sum as:
`TotalSum = Σ (for each i from 0 to n-1) [Contribution of subsets with nums[i] as max]`

The contribution for `nums[i]` as max is `nums[i]^2 * (Σ min(S))` for all subsets `S` where `max(S) = nums[i]`.

This can be broken down further. From the `O(n^2)` approach, we found the total sum is `Σ_{i=0..n-1} (nums[i]^3 + nums[i]^2 * Σ_{j=0..i-1} (nums[j] * 2^(i-j-1)))`.

Let's define a DP state `s_i = Σ_{j=0..i-1} (nums[j] * 2^(i-1-j))`. This `s_i` represents the weighted sum of previous minimums needed to calculate the contribution for `nums[i]`. We can find a recurrence for `s_i`:
`s_{i+1} = Σ_{j=0..i} (nums[j] * 2^(i-j)) = 2 * (Σ_{j=0..i-1} (nums[j] * 2^(i-1-j))) + nums[i] = 2 * s_i + nums[i]`.

This recurrence allows us to compute the necessary sum in `O(1)` time at each step of our iteration. We can maintain a single variable `s` that we update in each step.

```java
import java.util.Arrays;

class Solution {
    public int sumOfPower(int[] nums) {
        long MOD = 1_000_000_007;
        Arrays.sort(nums);
        
        long totalPower = 0;
        long s = 0; // Represents the running sum s_i
        
        for (int x : nums) {
            long x_long = x;
            
            // The contribution of all subsets where x is the maximum is:
            // (power of {x}) + (sum of powers of other subsets with max x)
            // This simplifies to x^3 + x^2 * s
            // which is x^2 * (x + s)
            long x_sq = (x_long * x_long) % MOD;
            long term = (x_long + s) % MOD;
            long contribution = (x_sq * term) % MOD;
            
            totalPower = (totalPower + contribution) % MOD;
            
            // Update s for the next element. The new s will be s_{i+1}.
            // s_new = 2 * s_old + x
            s = (s * 2 + x_long) % MOD;
        }
        
        // Ensure the result is positive
        return (int) ((totalPower + MOD) % MOD);
    }
}
```
### Algorithm
*   Sort the input array `nums`.
*   Initialize `totalPower = 0` and a helper variable `s = 0`. All calculations are modulo `10^9 + 7`.
*   Iterate through the sorted `nums` array. For each element `x` in `nums`:
    *   The contribution of all subsets where `x` is the maximum element is `x^2 * (x + s)`.
        *   The `x^3` part comes from the subset `{x}`.
        *   The `x^2 * s` part comes from the sum of powers of all subsets where `x` is the max and the min is some element smaller than `x`.
    *   Add this contribution to `totalPower`: `totalPower = (totalPower + (x^2 * (x + s))) % MOD`.
    *   Update the helper variable `s` for the next iteration. The new `s` is calculated based on the old `s` and the current element `x`: `s_new = (2 * s + x) % MOD`.
*   After iterating through all elements, return `totalPower`.

# Solutions
### Java

```java
class Solution {
public
  int sumOfPower(int[] nums) {
    final int mod = (int)1 e9 + 7;
    Arrays.sort(nums);
    long ans = 0, p = 0;
    for (int i = nums.length - 1; i >= 0; --i) {
      long x = nums[i];
      ans = (ans + (x * x % mod) * x) % mod;
      ans = (ans + x * p % mod) % mod;
      p = (p * 2 + x * x % mod) % mod;
    }
    return (int)ans;
  }
}

```

### Python

```python
class Solution:
    def sumOfPower(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 nums . sort() ans = 0 p = 0 for x in nums[:: - 1]: ans = (ans + (x * x % mod) * x) % mod ans = (ans + x * p) % mod p = (p * 2 + x * x) % mod return ans

```

### CPP

```cpp
class Solution {
public:
  int sumOfPower(vector<int> &nums) {
    const int mod = 1e9 + 7;
    sort(nums.rbegin(), nums.rend());
    long long ans = 0, p = 0;
    for (long long x : nums) {
      ans = (ans + (x * x % mod) * x) % mod;
      ans = (ans + x * p % mod) % mod;
      p = (p * 2 + x * x % mod) % mod;
    }
    return ans;
  }
};

```