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

Intuition

For each non-empty subset, the power is (max^2) * min. To avoid brute force, sort the array and use prefix sums. For each number as the maximum, count all subsets where it is the max, and use prefix sums to efficiently sum the min contributions.

Approach

  1. Sort nums. For each nums[i] as the maximum, all subsets of nums[0..i-1] can be combined with nums[i].
  2. For each such subset, the min is the minimum of the subset, and the max is nums[i].
  3. Use prefix sums to accumulate the sum of all possible min values for subsets ending at i-1.
  4. For each i, add (nums[i]^2) * (sum of all subset mins + nums[i]) to the answer.
  5. Return the answer modulo 1e9+7.

Code

C++
 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;
}
Go
 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
}
Java
 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 + x * x % MOD * (x + prefix) % MOD) % MOD;
            prefix = (2 * prefix % MOD + x) % MOD;
        }
        return (int)ans;
    }
}
Kotlin
 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()
}
Python
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
Rust
 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
}
TypeScript
 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;
}

Complexity

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