2681. Power of Heroes
Problem Description
The given problem involves calculating and summing the power of all non-empty groups of heroes based on their strength values provided in an integer array nums
. The power of a group is determined by the following:
- Identify the heroes in the group by their indices in the array, say iā, iā, ..., iā.
- The power of this group is the square of the maximum strength value among these heroes multiplied by the minimum strength value of the same heroes, i.e., max(nums[iā], nums[iā], ..., nums[iā])Ā² * min(nums[iā], nums[iā], ..., nums[iā]).
The goal is to add up the power of all possible non-empty groups of heroes. Since the result could be quite large, it should be returned modulo 10ā¹ + 7.
Intuition
To solve the problem, we need to figure out how to efficiently calculate the sum of the powers of all groups. Brute force enumeration of all groups would be too time-consuming due to the potentially large number of hero combinations. Instead, we can analyze the pattern of how the power of groups contributes to the total sum.
The solution revolves around observing that sorting the array nums
will make it easier to identify the maximums and minimums for different groups. Once sorted, any group with the last element as its maximum will have this last element as the maximum for all subsequent smaller subgroups ending with this element.
- Reverse iterate over the sorted
nums
. We count the contributions to the power from each element when it acts as both a maximum and minimum within different subgroups. - A running prefix sum
p
is kept. When a new elementx
is considered, it has an additional contribution when acting as the maximumādue to all possible subgroups ending withx
. Its contribution isx^3
added to all contributions from previous elements. - When
x
is a minimum, it addsx * p
to the result, wherep
includes the contributions from elements to the right ofx
in the sorted array when they act as maximums. - The prefix sum
p
is updated for the contribution ofx
being the maximum so far. It's the sum of all previousp
values doubled (since every subgroup comes in two variantsāwith and without the new elementx
) plus the square of the new elementx
(which is the new maximum for subgroups ending withx
).
The answer is computed by summing contributions while iterating through the array and using modulo arithmetic to handle large numbers.
Learn more about Math, Prefix Sum and Sorting patterns.
Solution Approach
The solution uses a simple array and basic arithmetic operations to calculate the required sum. The steps in the provided solution approach can be broken down as follows:
-
Sort the array ā Before iterating over
nums
, it is sorted in ascending order. This sorting enables us to find the maximums and minimums for subgroups based on their position in the sorted array. -
Initialize variables ā The solution sets an initial value for
ans
, which will hold the sum of powers, andp
, which is our running prefix sum representing the contributions of maximum values so far. -
Iterate in reverse ā The solution then iterates the sorted array in reverse (
nums[::-1]
), considering each number from largest to smallest, which aligns with how we consider maximums for subgroups.After entering the loop, it performs the following operations for every element
x
:-
Add to
ans
the value ofx
cubed (x * x % mod) * x
modulo10**9 + 7
. This covers the new subgroups wherex
is the maximum. -
Add to
ans
the value ofx
multiplied by the current prefix sump
, effectively capturing the contribution ofx
when it is the minimum value in a subgroup with any of the previous elements as the maximum. -
Update the prefix sum
p
by doubling it and adding the square of the current elementx
. Doubling accounts for the fact that each existing subgroup can now be extended by either including or excludingx
. Addingx*x
accounts for the new subgroups formed withx
as the maximum.
-
-
Modulo operations ā To handle potentially large numbers and overflow issues, modulo arithmetic is consistently applied (
% mod
) to ensure that all intermediate values and the resulting sum remain within integer limits.
By considering each element as the potential minimum and maximum of various subgroups, the solution efficiently accumulates the power of all possible combinations. The space complexity is optimal as it only uses a fixed number of variables and the original input array, while the time complexity is driven by the sorting operation and the subsequent linear traversal of the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach with the given problem:
Suppose we have an integer array of hero strengths nums = [2, 1, 3]
.
-
Sort the array: The first step is to sort
nums
to[1, 2, 3]
. -
Initialize variables: We initialize
ans
to 0, which will store the final answer, andp
to 0, which is the prefix sum of contributions when numbers act as maximums. -
Iterate in reverse: Now, we iterate from the end of the sorted array.
At the start,
ans = 0
andp = 0
. We go through each elementx
innums[::-1]
(which gives us[3, 2, 1]
) and perform the next steps.-
For
x = 3
:- Update
ans
by adding3^3 % (10^9 + 7) = 27
. p
gets updated to2 * p + x^2 = 0 + 3^2 = 9
.
- Update
-
For
x = 2
:- Update
ans
by adding both2^3 % (10^9 + 7) = 8
and2 * p = 2 * 9 = 18
. Now,ans = ans + 8 + 18 = 27 + 26 = 53
. - Update
p
to2 * p + x^2 = 2 * 9 + 2^2 = 18 + 4 = 22
.
- Update
-
For
x = 1
:- Update
ans
by adding both1^3 % (10^9 + 7) = 1
and1 * p = 1 * 22 = 22
. Now,ans = 53 + 1 + 22 = 76
. - Update
p
to2 * p + x^2 = 2 * 22 + 1^2 = 44 + 1 = 45
.
- Update
-
-
Modulo operations: Always use modulo
10^9 + 7
during the addition to keep the numbers within bounds. However, in our small example, the answers are still small, so we don't need to apply modulo.
After iterating through all elements, we have the final ans = 76
. This is the sum of the power of all possible non-empty groups of heroes calculated with the given formula, and since the value is already less than 10^9 + 7
, we don't need to apply the modulo operation in this example.
In a larger example, if at any step the value of ans
or p
exceeds 10^9 + 7
, we would take ans % (10^9 + 7)
or p % (10^9 + 7)
respectively to keep the values within the limit.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sumOfPower(self, nums: List[int]) -> int:
5 # Define the modulo to perform operations under
6 modulo = 10**9 + 7
7 # Sort the list of numbers in non-descending order
8 nums.sort()
9 # Initialize the answer variable to accumulate the sum of powers
10 answer = 0
11 # Initialize a variable 'power_sum' to store the accumulated powers of elements
12 power_sum = 0
13 # Iterate over the numbers in reverse (largest to smallest)
14 for num in reversed(nums):
15 # For each number, add the cubed value (mod modulo) multiplied by the number to the answer
16 answer = (answer + (num * num % modulo) * num) % modulo
17 # Add the current number times the accumulated power_sum to the answer
18 answer = (answer + num * power_sum) % modulo
19 # Update the power_sum with the current num squared plus twice the previous power_sum
20 power_sum = (power_sum * 2 + num * num) % modulo
21 # Return the computed answer
22 return answer
23
1class Solution {
2 public int sumOfPower(int[] nums) {
3 // Define the modulus value for large numbers to stay within the integer bounds
4 final int MOD = (int) 1e9 + 7;
5
6 // Sort the input array in ascending order
7 Arrays.sort(nums);
8
9 // Initialize the answer as 0 and a helper variable p to compute powers
10 long answer = 0;
11 long powers = 0;
12
13 // Iterate over the array in reverse to compute the sum of powers
14 for (int i = nums.length - 1; i >= 0; --i) {
15 long currentNum = nums[i];
16
17 // Compute the contribution of the current number raised to the power of 3
18 // Make sure to take the modulo to prevent integer overflow
19 answer = (answer + (currentNum * currentNum % MOD) * currentNum) % MOD;
20
21 // Add the contribution of the current number times the partial sum of powers (p)
22 // Again, use modulo to avoid overflow
23 answer = (answer + currentNum * powers % MOD) % MOD;
24
25 // Update p to be 2 times itself plus the current number squared (mod MOD)
26 powers = (powers * 2 + currentNum * currentNum % MOD) % MOD;
27 }
28
29 // Cast the long result back to int before returning, as per the method signature expectation
30 return (int) answer;
31 }
32}
33
1class Solution {
2public:
3 int sumOfPower(vector<int>& nums) {
4 const int MOD = 1e9 + 7; // define modulo value to prevent integer overflow
5 sort(nums.rbegin(), nums.rend()); // sort the numbers in descending order
6
7 long long totalSum = 0; // holds the total sum result
8 long long powerSum = 0; // holds the sum of squares, multiplied by 2 each iteration
9
10 // Iterate through all the numbers in the vector
11 for (long long num : nums) {
12 // Add to totalSum the current number cubed, modulo MOD
13 totalSum = (totalSum + (num * num % MOD) * num) % MOD;
14
15 // Add to totalSum the current number multiplied by powerSum, modulo MOD
16 totalSum = (totalSum + num * powerSum % MOD) % MOD;
17
18 // Update powerSum by multiplying by 2 and adding the current number squared, modulo MOD
19 powerSum = (powerSum * 2 + num * num % MOD) % MOD;
20 }
21
22 return static_cast<int>(totalSum); // cast totalSum to int and return the final answer
23 }
24};
25
1function sumOfCubedPowers(nums: number[]): number {
2 // The modulo to use for preventing overflow
3 const MODULO = 10 ** 9 + 7;
4
5 // Sort the numbers array in ascending order
6 nums.sort((a, b) => a - b);
7
8 // Initialize the answer to 0
9 let answer = 0;
10
11 // Initialize the prefix sum, representing sum of powers
12 let prefixSum = 0;
13
14 // Iterate over the array in reverse
15 for (let i = nums.length - 1; i >= 0; --i) {
16 // Get the current number as a BigInt for precision in calculations
17 const currentNum = BigInt(nums[i]);
18
19 // Add the cube of the current number modulo MODULO to the answer
20 answer = (answer + Number((currentNum * currentNum * currentNum) % BigInt(MODULO))) % MODULO;
21
22 // Add the product of the currentNum and the prefixSum modulo MODULO to the answer
23 answer = (answer + Number((currentNum * BigInt(prefixSum)) % BigInt(MODULO))) % MODULO;
24
25 // Update the prefixSum: multiply by 2 and add the square of currentNum
26 prefixSum = Number((BigInt(prefixSum) * 2n + currentNum * currentNum) % BigInt(MODULO));
27 }
28
29 // Return the final answer
30 return answer;
31}
32
Time and Space Complexity
Time Complexity
The time complexity of the provided function is determined by a few key operations:
-
Sorting the
nums
list: Thesort()
function has a time complexity ofO(n log n)
wheren
is the number of elements in the list. -
The for-loop that iterates over the sorted list in reverse: The loop runs
n
times, wheren
is the length ofnums
.Inside the loop, all operations are constant time (
O(1)
), as they involve basic arithmetic operations and modulo%
operation, which do not depend on the size ofnums
.Combining these constants with the iteration gives us
O(n)
for the loop.
Combining both operations, the total time complexity of the code is O(n log n)
for sorting the list plus O(n)
for the loop, which simplifies to O(n log n)
overall, as O(n log n)
is the dominating term.
Space Complexity
The space complexity of the provided function is determined by:
-
The additional space used by the sorting algorithm. Most Python implementations use an in-place sorting algorithm, like Timsort, which would make the space complexity of sorting
O(n)
in the worst case. However, the sorted list uses the same space that was allocated fornums
, so this may not count as additional space. -
Variables
ans
,p
, andmod
occupyO(1)
space as they store integers that don't depend on the size of the input list. -
The loop itself does not use any additional space that depends on
n
(no new list or data structure is being created that grows with the input).
Considering the above points, the space complexity of the function is O(1)
for the variables defined outside the loop since they do not use additional space dependent on the input list size. However, taking into account the potential additional space required for sorting (if interpreted as additional space rather than in-place), it could be argued to be O(n)
in a pessimistic assessment.
Overall, if the sort is considered in-place, the space complexity is O(1)
; otherwise, it may be O(n)
in the worst case.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!