Maximum Points After Enemy Battles - Practice Coding Problems

Maximum Points After Enemy Battles - Problem

Array Greedy Medium

You are given an integer array enemyEnergies denoting the energy values of various enemies. You are also given an integer currentEnergy denoting the amount of energy you have initially.

You start with 0 points, and all the enemies are unmarked initially. You can perform either of the following operations zero or multiple times to gain points:

Option 1: Choose an unmarked enemy i such that currentEnergy >= enemyEnergies[i]. By choosing this option:

You gain 1 point
Your energy is reduced by the enemy's energy: currentEnergy = currentEnergy - enemyEnergies[i]

Option 2: If you have at least 1 point, you can choose an unmarked enemy i. By choosing this option:

Your energy increases by the enemy's energy: currentEnergy = currentEnergy + enemyEnergies[i]
The enemy i is marked

Return an integer denoting the maximum points you can get in the end by optimally performing operations.

Input & Output

Example 1 — Basic Strategy

$ Input: enemyEnergies = [3,2,4], currentEnergy = 11

› Output: 9

💡 Note: Defeat enemy with energy 2 (weakest) → gain 1 point, energy becomes 9. Absorb enemies with energy 3 and 4 → energy becomes 9+3+4=16. Defeat weakest enemy (energy 2) repeatedly: 16÷2=8 more times. Total points = 1+8 = 9.

Example 2 — Insufficient Energy

$ Input: enemyEnergies = [4,3,5], currentEnergy = 2

› Output: 0

💡 Note: Current energy (2) is less than the minimum enemy energy (3), so we cannot defeat any enemy to get our first point. Result is 0 points.

Example 3 — Single Enemy

$ Input: enemyEnergies = [5], currentEnergy = 10

› Output: 2

💡 Note: Only one enemy with energy 5. Defeat it once → gain 1 point, energy becomes 5. Since we now have 1 point, we can absorb the same enemy → energy becomes 5+5=10. Defeat it again: 10÷5=2 times. But wait, we already used it, so total = 1+(10-5)÷5 = 2.

Constraints

1 ≤ enemyEnergies.length ≤ 10⁵
1 ≤ enemyEnergies[i] ≤ 10⁹
0 ≤ currentEnergy ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of enemy energies and current energy

Strategy

Defeat weakest, absorb others, repeat defeats

Output

Maximum points achievable

Key Takeaway

🎯 Key Insight: Always defeat the weakest enemy first to unlock absorption, then absorb stronger enemies to maximize energy for more defeats

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to defeat the weakest enemy first to unlock absorption ability, then absorb all other enemies to maximize energy, and finally defeat the weakest enemy repeatedly. Best approach is greedy strategy with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2ⁿ)	O(n)	Try all possible sequences of operations recursively
Greedy Strategy	O(n)	O(1)	Defeat weakest enemy first, then absorb all others optimally

Brute Force Simulation — Algorithm Steps

Step 1: For each unmarked enemy, try defeating it if we have enough energy
Step 2: For each unmarked enemy, try absorbing it if we have at least 1 point
Step 3: Recursively explore all possibilities and return maximum points

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with current energy and 0 points

Branch Decision

Try defeating or absorbing each enemy

Recursive Exploration

Explore all paths to find maximum points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int backtrack(int* enemyEnergies, int n, bool* marked, int energy, int points) {
    int maxPoints = points;
    
    // Try defeating each unmarked enemy
    for (int i = 0; i < n; i++) {
        if (!marked[i] && energy >= enemyEnergies[i]) {
            int newPoints = backtrack(enemyEnergies, n, marked, energy - enemyEnergies[i], points + 1);
            if (newPoints > maxPoints) {
                maxPoints = newPoints;
            }
        }
    }
    
    // Try absorbing each unmarked enemy (if we have points)
    if (points > 0) {
        for (int i = 0; i < n; i++) {
            if (!marked[i]) {
                marked[i] = true;
                int newPoints = backtrack(enemyEnergies, n, marked, energy + enemyEnergies[i], points);
                if (newPoints > maxPoints) {
                    maxPoints = newPoints;
                }
                marked[i] = false;
            }
        }
    }
    
    return maxPoints;
}

int solution(int* enemyEnergies, int n, int currentEnergy) {
    bool* marked = (bool*)calloc(n, sizeof(bool));
    int result = backtrack(enemyEnergies, n, marked, currentEnergy, 0);
    free(marked);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int enemyEnergies[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        enemyEnergies[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int currentEnergy;
    scanf("%d", &currentEnergy);
    
    printf("%d\n", solution(enemyEnergies, n, currentEnergy));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each enemy can be defeated, absorbed, or left unmarked, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels plus array to track marked enemies

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

247 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler