Scale Engineer

Power of Heroes

Hard
#2430Time: 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)`.
Patterns
MathDynamic ProgrammingPrefix Sum
Algorithms
Sorting
Data structures
Array

Prompt

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.

 

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 <= 105
  • 1 <= 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 totalPower to 0.
  • Define a recursive function, say generateSubsets(index, currentSubset), to generate all subsets.
  • The function takes the current index in the nums array and the currentSubset being built.
  • Base Case: When index reaches the end of the array, check if currentSubset is non-empty.
    • If it is, find its minimum and maximum elements.
    • Calculate the power: power = (max^2 * min) % MOD.
    • Add this power to totalPower.
  • Recursive Step: For each element nums[index], make two recursive calls:
    1. One call that excludes nums[index] from the subset: generateSubsets(index + 1, currentSubset).
    2. One call that includes nums[index] in the subset: add nums[index] to currentSubset, call generateSubsets(index + 1, currentSubset), and then remove nums[index] (backtracking).
  • 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

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.

← Previous

Previous problem

Next →

Next problem