Problem

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 thepower of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1
2
3

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

Solution

Method 1 - Sort + Prefix Sums (Max-as-Pivot)

Intuition

For each non-empty subset, the power is (max^2) * min. To avoid brute force, sort the array nums and use prefix sums. Treat each element x as the maximum, and count all subsets where x is the max; use a running prefix to accumulate contributions from smaller elements efficiently and update ans modulo MOD.

Approach

  1. Sort nums.
  2. Iterate over each element x in nums (as the maximum).
  3. Maintain a running prefix that equals the sum of all subset-min contributions from prior elements (updated as prefix = 2*prefix + x modulo MOD).
  4. For each x, add (x^2) * (x + prefix) to ans (mod MOD).
  5. Return ans modulo MOD.

Complexity

  • ⏰ Time complexity: O(n log n) for sorting and O(n) for the main loop.
  • 🧺 Space complexity: O(1) (ignoring input/output).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
int sumOfPower(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    ll ans = 0, prefix = 0;
    for (int x : nums) {
        ans = (ans + (ll)x * x % MOD * (x + prefix) % MOD) % MOD;
        prefix = (2 * prefix + x) % MOD;
    }
    return (int)ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import "sort"
func sumOfPower(nums []int) int {
    sort.Ints(nums)
    const MOD = 1_000_000_007
    ans, prefix := 0, 0
    for _, x := range nums {
        ans = (ans + x * x % MOD * (x + prefix) % MOD) % MOD
        prefix = (2 * prefix % MOD + x) % MOD
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public int sumOfPower(int[] nums) {
        Arrays.sort(nums);
        long ans = 0, prefix = 0, MOD = 1_000_000_007;
        for (int x : nums) {
            ans = (ans + ((long)x * x % MOD) * ((x + prefix) % MOD)) % MOD;
            prefix = (2 * prefix % MOD + x) % MOD;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fun sumOfPower(nums: IntArray): Int {
    nums.sort()
    val MOD = 1_000_000_007L
    var ans = 0L
    var prefix = 0L
    for (x in nums) {
        ans = (ans + x * x % MOD * (x + prefix) % MOD) % MOD
        prefix = (2 * prefix % MOD + x) % MOD
    }
    return ans.toInt()
}
1
2
3
4
5
6
7
8

def sumOfPower(nums: list[int]) -> int:
    nums.sort()
    MOD = 10**9 + 7
    ans = prefix = 0
    for x in nums:
        ans = (ans + x * x % MOD * (x + prefix) % MOD) % MOD
        prefix = (2 * prefix + x) % MOD
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fn sum_of_power(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let mut ans: i64 = 0;
    let mut prefix: i64 = 0;
    let m = 1_000_000_007;
    for &x in &nums {
        let x = x as i64;
        ans = (ans + x * x % m * (x + prefix) % m) % m;
        prefix = (2 * prefix % m + x) % m;
    }
    ans as i32
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

export function sumOfPower(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const MOD = 1_000_000_007;
    let ans = 0, prefix = 0;
    for (const x of nums) {
        ans = (ans + x * x % MOD * (x + prefix) % MOD) % MOD;
        prefix = (2 * prefix % MOD + x) % MOD;
    }
    return ans;
}