Power of heroes

Array Math Dynamic Programming Sorting Prefix Sum

31.3% acceptance

Feb 25, 2026

337

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_power(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut nums = nums;
    nums.sort_unstable();
    let mut ans = 0i64;
    let mut s = 0i64; // running sum for prefix contribution
    for &v in &nums {
      let v = v as i64;
      // contribution: v^2 * (v + s)
      ans = (ans + v % MOD * (v % MOD) % MOD * ((v + s) % MOD)) % MOD;
      s = (2 * s + v) % MOD;
    }
    ans as i32
  }
}