Minimum Amount of Damage Dealt to Bob - Practice Coding Problems

Minimum Amount of Damage Dealt to Bob - Problem

You are given an integer power and two integer arrays damage and health, both having length n.

Bob has n enemies, where enemy i will deal Bob damage[i] points of damage per second while they are alive (i.e. health[i] > 0).

Every second, after the enemies deal damage to Bob, he chooses one of the enemies that is still alive and deals power points of damage to them.

Determine the minimum total amount of damage points that will be dealt to Bob before all n enemies are dead.

Input & Output

Example 1 — Basic Case

$ Input: power = 10, damage = [10,4,15], health = [80,20,40]

› Output: 138

💡 Note: Enemy ratios: 10/8=1.25, 4/2=2.0, 15/4=3.75. Attack order [2,1,0] gives minimum damage of 138.

Example 2 — Equal Ratios

$ Input: power = 5, damage = [5,10], health = [10,20]

› Output: 30

💡 Note: Both enemies have ratio 5/2=2.5. Either order works, total damage is 30.

Example 3 — Single Enemy

$ Input: power = 20, damage = [15], health = [30]

› Output: 30

💡 Note: Only one enemy: takes 2 turns to kill, deals 15 damage per turn, total 30.

Constraints

1 ≤ power ≤ 10⁴
1 ≤ n ≤ 10⁵
1 ≤ damage[i], health[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Battle Setup

Bob faces multiple enemies, each dealing damage per turn

Turn Mechanics

Enemies attack first, then Bob attacks one enemy

Optimal Strategy

Attack enemies with highest damage/time ratio first

Key Takeaway

🎯 Key Insight: Prioritize enemies by damage-per-time ratio to minimize total damage taken

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to use a greedy approach: prioritize attacking enemies by their damage-per-time-to-kill ratio. Calculate each enemy's time to kill as ceil(health/power), then sort enemies by damage/time ratio in descending order. Attack in this optimal order to minimize total damage. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Optimal Priority Order	O(n log n)	O(n)	Sort enemies by damage/time_to_kill ratio and attack in optimal order
Brute Force - Try All Orders	O(n! × n²)	O(n)	Try all possible orders of defeating enemies and find minimum damage

Greedy - Optimal Priority Order — Algorithm Steps

Step 1: Calculate time to kill each enemy (ceil(health/power))
Step 2: Sort enemies by damage/time_to_kill ratio in descending order
Step 3: Simulate battle attacking enemies in this optimal order

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Ratios

For each enemy, compute damage per time to kill

Sort by Priority

Sort enemies by damage/time ratio in descending order

Attack in Order

Attack enemies following the optimal priority order

Code -

solution.c — C

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

typedef struct {
    double ratio;
    int damage;
    int health;
    int index;
} Enemy;

int compareEnemies(const void* a, const void* b) {
    Enemy* enemyA = (Enemy*)a;
    Enemy* enemyB = (Enemy*)b;
    if (enemyB->ratio > enemyA->ratio) return 1;
    if (enemyB->ratio < enemyA->ratio) return -1;
    return 0;
}

long long solution(int power, int* damage, int* health, int n) {
    // Calculate time to kill each enemy and create priority list
    Enemy* enemies = (Enemy*)malloc(n * sizeof(Enemy));
    for (int i = 0; i < n; i++) {
        int timeToKill = (health[i] + power - 1) / power; // Ceiling division
        double ratio = timeToKill > 0 ? (double)damage[i] / timeToKill : 1e9;
        enemies[i] = (Enemy){ratio, damage[i], health[i], i};
    }
    
    // Sort by ratio in descending order (highest priority first)
    qsort(enemies, n, sizeof(Enemy), compareEnemies);
    
    // Simulate the battle
    long long totalDamage = 0;
    int* enemyHealth = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) enemyHealth[i] = health[i];
    
    int* enemiesAlive = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) enemiesAlive[i] = 1;
    int aliveCount = n;
    
    // Create attack order based on sorted priorities
    int* attackOrder = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        attackOrder[i] = enemies[i].index;
    }
    int orderIdx = 0;
    
    while (aliveCount > 0) {
        // All alive enemies deal damage
        long long currentDamage = 0;
        for (int i = 0; i < n; i++) {
            if (enemiesAlive[i]) {
                currentDamage += damage[i];
            }
        }
        totalDamage += currentDamage;
        
        // Find next target that's still alive
        while (orderIdx < n && !enemiesAlive[attackOrder[orderIdx]]) {
            orderIdx++;
        }
        
        if (orderIdx < n) {
            int target = attackOrder[orderIdx];
            enemyHealth[target] -= power;
            
            if (enemyHealth[target] <= 0) {
                enemiesAlive[target] = 0;
                aliveCount--;
                orderIdx++;
            }
        }
    }
    
    free(enemies);
    free(enemyHealth);
    free(enemiesAlive);
    free(attackOrder);
    return totalDamage;
}

int main() {
    int power;
    scanf("%d", &power);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    // Parse damage array
    int damage[100];
    int damageCount = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        damage[damageCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf(" %[^\n]", line);
    
    // Parse health array
    int health[100];
    int healthCount = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        health[healthCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(power, damage, health, damageCount);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting enemies by damage/time ratio takes O(n log n), simulation takes O(n²)

⚡ Linearithmic

Space Complexity

O(n)

Storage for enemy data and sorting

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~35 min Avg. Time

850 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

Greedy - Optimal Priority Order — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler