DSA SheetHard
EditorialPractice

PREFIX SUM › PREFIX SUM

Power of Heroes

HardEditorial · 8 minGenerated by gpt-5.6-luna · Aug 29

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionassigning every group to one sorted maximum

Sort the strengths from smallest to largest. Consider a group whose largest selected element is nums[i]. Its power always contains nums[i] squared, so the remaining question is the sum of the possible minimum strengths for groups assigned to this maximum. Assign a group to the rightmost maximum it contains; this makes the assignment unique even when several strengths are equal.

If nums[j] is the minimum and j is at most i, both endpoints must be selected, every index between them may be selected or skipped, and every index after i must be skipped. There are 2^(i - j - 1) choices for the interior. Thus nums[j] is weighted by that power of two, and the total contribution for maximum i is nums[i] squared times the weighted minimum sum.

a sorted array with a fixed maximum and possible minimumsThe drawing shows a sorted array laid out from left to right. A candidate minimum nums[j] is highlighted on the left, a fixed maximum nums[i] is highlighted on the right, and the values between them form an interior range whose elements can be selected or skipped independently. When the maximum moves one position right, the old groups can either include or exclude the new position, so their accumulated minimum contribution doubles. The picture makes the recurrence s = nums[i] + 2s visible.12345813candidate minimumnums[j] = 2 (j = 1)fixed maximumnums[i] = 8 (i = 5)W = weighted prefix sum before nums[i]selected endpointselected endpoint0123456interior j + 1 … i − 1: independently selectableW doubles: include /exclude

Approachturning the subset count into one running value

  1. Sort nums so every processed element is at least as large as the elements before it; without this order, an earlier element would not reliably be the minimum and the current element would not reliably be the assigned maximum.
  2. Maintain s as the sum of minimum strengths for all groups formed from already processed elements, with the weighting needed when the next maximum is considered; this avoids recomputing every possible minimum.
  3. For the current value x, add x squared times x for the singleton group; omitting this term loses the group whose minimum and maximum are both x.
  4. Add x squared times s for all groups that already contain an earlier minimum and now use x as their maximum; each such group's power gains the factor x squared.
  5. Update s to x + 2s after using it. The x creates the singleton group for future maxima, while 2s accounts for choosing or skipping the current x in every older group.
  6. Take every multiplication modulo 1e9 + 7 and use long long for intermediate products; int multiplication can overflow before the remainder is taken.
  7. Return ans after the scan, because each group has been assigned to exactly one rightmost selected maximum and has therefore contributed once.

Complexitysorting dominates the scan

MEASUREBOUNDWHY
TimeO(n log n)Sorting performs the dominant work on n elements, and the following scan visits each element once. No subset is enumerated: all of the 2^n groups are represented by the one running sum.
SpaceO(log n) extraThe array is sorted in place, and the scan uses only a constant number of variables. The standard comparison sort may use O(log n) stack space; unlike a recursive structure, this bound does not degrade for any particular input shape. Output storage is excluded because the required result is one integer.
Here n is the number of heroes. The returned value is a single integer and is excluded from extra-space usage.

Annotated solutionC++ · sorted one-pass prefix recurrence

CPPSort first, then use s to add every group whose assigned maximum is the current value.
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        const long long MOD = 1000000007LL;
        sort(nums.begin(), nums.end());

        long long ans = 0;
        long long s = 0;

        for (int x : nums) {
            long long value = x;
            ans = (ans + value * value % MOD * (value + s) % MOD) % MOD;
            s = (value + 2 * s) % MOD;
        }

        return static_cast<int>(ans);
    }
};

The order of the two lines inside the loop matters. ans uses the old s, which describes groups made before x was considered. Only after those groups receive x squared as their maximum do you update s so that future maxima can extend them. Updating s first would count x as part of the current maximum's minimum combinations and change the weights.

Common mistakesthree lines that quietly change the counting

Previous · Increment Submatrices by One