Power of Heroes
HardPrompt
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, ... ,ikbe the indices of the heroes in a group. Then, the power of this group ismax(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.
Example 1:
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:
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 <= 1051 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve the problem is to generate every possible non-empty group (subset) of heroes, calculate the power for each group, and sum them up. This can be achieved by iterating through all 2^n - 1 non-empty subsets.
Algorithm
- Initialize a global variable
totalPowerto 0. - Define a recursive function, say
generateSubsets(index, currentSubset), to generate all subsets. - The function takes the current
indexin thenumsarray and thecurrentSubsetbeing built. - Base Case: When
indexreaches the end of the array, check ifcurrentSubsetis non-empty.- If it is, find its minimum and maximum elements.
- Calculate the power:
power = (max^2 * min) % MOD. - Add this
powertototalPower.
- Recursive Step: For each element
nums[index], make two recursive calls:- One call that excludes
nums[index]from the subset:generateSubsets(index + 1, currentSubset). - One call that includes
nums[index]in the subset: addnums[index]tocurrentSubset, callgenerateSubsets(index + 1, currentSubset), and then removenums[index](backtracking).
- One call that excludes
- Start the process by calling
generateSubsets(0, new ArrayList<>()). - Return
totalPower.
Walkthrough
This approach uses recursion with backtracking to explore all possible combinations of heroes. We define a helper function that builds subsets element by element. For each element in the input array nums, we decide whether to include it in the current subset or not. This creates two branches at each step, leading to 2^n total subsets. Once a complete subset is formed (i.e., we've made a decision for every hero), we check if it's non-empty. If it is, we iterate through the subset to find its minimum and maximum strength values. We then compute its power using the formula max_strength^2 * min_strength and add it to a running total. All additions are performed modulo 10^9 + 7 to prevent overflow.
class Solution { long totalPower = 0; int MOD = 1_000_000_007; public int sumOfPower(int[] nums) { List<Integer> currentSubset = new ArrayList<>(); generateSubsets(nums, 0, currentSubset); return (int) totalPower; } private void generateSubsets(int[] nums, int index, List<Integer> currentSubset) { if (index == nums.length) { if (!currentSubset.isEmpty()) { long minVal = Long.MAX_VALUE; long maxVal = Long.MIN_VALUE; for (int num : currentSubset) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } long maxSq = (maxVal * maxVal) % MOD; long power = (maxSq * minVal) % MOD; totalPower = (totalPower + power) % MOD; } return; } // Decision 1: Exclude nums[index] generateSubsets(nums, index + 1, currentSubset); // Decision 2: Include nums[index] currentSubset.add(nums[index]); generateSubsets(nums, index + 1, currentSubset); currentSubset.remove(currentSubset.size() - 1); // Backtrack }}Complexity
Time
O(n * 2^n) There are `2^n` possible subsets. For each subset, we iterate through its elements to find the minimum and maximum, which takes `O(k)` time where `k` is the subset size (up to `n`). This results in an overall time complexity of `O(n * 2^n)`.
Space
O(n) The space complexity is determined by the depth of the recursion stack, which is `O(n)`, and the space required to store the `currentSubset`, which can also be up to `O(n)`.
Trade-offs
Pros
Conceptually simple and easy to understand.
Correct for small input sizes.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the constraints specified in the problem.
Solutions
Solution
class Solution {public int sumOfPower(int[] nums) { final int mod = (int)1 e9 + 7; Arrays.sort(nums); long ans = 0, p = 0; for (int i = nums.length - 1; i >= 0; --i) { long x = nums[i]; ans = (ans + (x * x % mod) * x) % mod; ans = (ans + x * p % mod) % mod; p = (p * 2 + x * x % mod) % mod; } return (int)ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.