# Minimum Amount of Damage Dealt to Bob
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-amount-of-damage-dealt-to-bob)
Canonical: https://scaleengineer.com/dsa/problems/minimum-amount-of-damage-dealt-to-bob
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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_.

**Example 1:**

**Input:** power = 4, damage = \[1,2,3,4\], health = \[4,5,6,8\]

**Output:** 39

**Explanation:**

* Attack enemy 3 in the first two seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is `10 + 10 = 20` points.
* Attack enemy 2 in the next two seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is `6 + 6 = 12` points.
* Attack enemy 0 in the next second, after which enemy 0 will go down, the number of damage points dealt to Bob is `3` points.
* Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is `2 + 2 = 4` points.

**Example 2:**

**Input:** power = 1, damage = \[1,1,1,1\], health = \[1,2,3,4\]

**Output:** 20

**Explanation:**

* Attack enemy 0 in the first second, after which enemy 0 will go down, the number of damage points dealt to Bob is `4` points.
* Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is `3 + 3 = 6` points.
* Attack enemy 2 in the next three seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is `2 + 2 + 2 = 6` points.
* Attack enemy 3 in the next four seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is `1 + 1 + 1 + 1 = 4` points.

**Example 3:**

**Input:** power = 8, damage = \[40\], health = \[59\]

**Output:** 320

**Constraints:**

* `1 <= power <= 104`
* `1 <= n == damage.length == health.length <= 105`
* `1 <= damage[i], health[i] <= 104`

# Approaches
## Brute Force by Generating All Permutations
The problem asks for an optimal order to defeat enemies to minimize total damage. A straightforward but naive approach is to try every possible order. We can generate all permutations of the enemies, calculate the total damage for each specific order, and then find the minimum among them.
**Time:** O(n! * n) - There are `n!` permutations to generate. For each permutation, we perform a calculation that takes O(n) time. This makes the total complexity O(n * n!). · **Space:** O(n) - The space is used to store the current permutation and for the recursion stack, both of which go up to a depth of `n`.
**Pros:** Conceptually simple to understand.; Guaranteed to find the optimal solution by checking every possibility.
**Cons:** Extremely inefficient due to its factorial time complexity.; Only feasible for very small values of `n` (e.g., n <= 10), and will time out for the given constraints.
### Explanation
The core idea of this approach is to explore the entire search space of `n!` possible orderings of enemies. Since any order is a permutation of the `n` enemies, we can generate all of them and find the one that yields the minimum damage.

First, we pre-calculate the time `t_i` required to defeat each enemy `i`, which is `ceil(health[i] / power)`. This can be computed using integer arithmetic as `(health[i] + power - 1) / power`.

We then use a recursive function to generate all permutations of the enemy indices `[0, 1, ..., n-1]`. For each complete permutation, we simulate the battle from start to finish:

1.  Initialize `total_damage_for_this_order` to 0.
2.  Initialize `current_dps` to the sum of all enemies' damages.
3.  Iterate through the enemies in the order given by the current permutation.
4.  For each enemy, calculate the damage Bob takes while he is focused on defeating this enemy. This damage is `t_i * current_dps`.
5.  Add this to `total_damage_for_this_order`.
6.  After an enemy is defeated, subtract its damage from `current_dps` for the next stage of the battle.

We maintain a global minimum variable, updating it whenever we find an ordering that results in less total damage. While correct, this method is computationally expensive.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    long minDamage = Long.MAX_VALUE;
    int n;
    int[] damage;
    long[] timeToKill;

    public long minimumDamage(int power, int[] damage, int[] health) {
        this.n = damage.length;
        this.damage = damage;
        this.timeToKill = new long[n];
        for (int i = 0; i < n; i++) {
            timeToKill[i] = (long)(health[i] + power - 1) / power;
        }

        permute(new ArrayList<>(), new boolean[n]);
        return minDamage;
    }

    private void permute(List<Integer> currentOrder, boolean[] visited) {
        if (currentOrder.size() == n) {
            calculateDamage(currentOrder);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                currentOrder.add(i);
                permute(currentOrder, visited);
                currentOrder.remove(currentOrder.size() - 1);
                visited[i] = false; // backtrack
            }
        }
    }

    private void calculateDamage(List<Integer> order) {
        long currentTotalDamage = 0;
        long currentDps = 0;
        for (int d : damage) {
            currentDps += d;
        }

        for (int enemyIndex : order) {
            currentTotalDamage += timeToKill[enemyIndex] * currentDps;
            currentDps -= damage[enemyIndex];
        }
        minDamage = Math.min(minDamage, currentTotalDamage);
    }
}
```
### Algorithm
- Calculate `t_i = (health[i] + power - 1) / power` for each enemy `i`.
- Use a recursive helper function to generate all `n!` permutations of enemy indices `(0, 1, ..., n-1)`.
- For each complete permutation `p`:
  - Initialize `total_damage = 0`.
  - Initialize `current_dps = sum(damage)`.
  - For each enemy index `j` in the permutation `p`:
    - Add the damage incurred during this step: `total_damage += t_j * current_dps`.
    - Update the dps for the next step: `current_dps -= damage[j]`.
  - Keep track of the minimum `total_damage` found across all permutations.
- Return the overall minimum damage.

## Dynamic Programming with Bitmask
This approach improves upon brute force by using dynamic programming with bitmasking to avoid recomputing results for the same subset of defeated enemies. We use a bitmask to represent the set of defeated enemies, and the DP state `dp[mask]` stores the minimum damage to defeat the enemies in that set.
**Time:** O(n * 2^n) - We iterate through `2^n` masks. For each mask, we iterate up to `n` times to check each bit and compute the transition. · **Space:** O(2^n) - We need to store the `dp` table of size `2^n` and a `damageSum` table of the same size.
**Pros:** Much faster than brute force.; Systematically builds the solution from smaller subproblems, avoiding redundant calculations.
**Cons:** The exponential time and space complexity make it infeasible for the given constraint `n <= 10^5`.; It would only pass for `n` up to around 20.
### Explanation
A more optimized approach than brute force is to use dynamic programming. We can define a state `dp[mask]` as the minimum total damage Bob receives to defeat the set of enemies represented by the bitmask `mask`. A mask is an integer where the `i`-th bit is 1 if enemy `i` has been defeated, and 0 otherwise.

The transition logic considers how a state `mask` is reached. It must be reached from a state with one fewer enemy defeated. Let's say enemy `k` was the *last* one to be defeated to form the set `mask`. This means we first defeated all enemies in `mask` except `k` (represented by `prev_mask = mask ^ (1 << k)`), and then we defeated enemy `k`.

The total damage to reach state `mask` by defeating `k` last is:
1.  The minimum damage to defeat enemies in `prev_mask`, which is `dp[prev_mask]`.
2.  The damage incurred while defeating enemy `k`. At this point, all enemies *not* in `prev_mask` are alive. The total DPS is the sum of damages of these alive enemies. The time to kill `k` is `t_k`. So, this damage is `t_k * (sum of damages of all enemies not in prev_mask)`.

We can precompute the sum of damages for every subset to quickly find the DPS at any stage. The recurrence relation becomes:
`dp[mask] = min_{k in mask} (dp[mask ^ (1 << k)] + t_k * (total_dps - damageSum[mask ^ (1 << k)]))`

The base case is `dp[0] = 0`. The final answer is `dp[(1 << n) - 1]`.

```java
import java.util.Arrays;

class Solution {
    public long minimumDamage(int power, int[] damage, int[] health) {
        int n = damage.length;
        long[] timeToKill = new long[n];
        long totalInitialDps = 0;
        for (int i = 0; i < n; i++) {
            timeToKill[i] = (long)(health[i] + power - 1) / power;
            totalInitialDps += damage[i];
        }

        long[] damageSum = new long[1 << n];
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    damageSum[mask] += damage[i];
                }
            }
        }

        long[] dp = new long[1 << n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    int prevMask = mask ^ (1 << i);
                    if (dp[prevMask] != Long.MAX_VALUE) {
                        long damageWhileKillingI = timeToKill[i] * (totalInitialDps - damageSum[prevMask]);
                        long newTotalDamage = dp[prevMask] + damageWhileKillingI;
                        dp[mask] = Math.min(dp[mask], newTotalDamage);
                    }
                }
            }
        }

        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- Calculate `t_i = (health[i] + power - 1) / power` for each enemy `i`.
- Precompute `damageSum[mask]` for all `2^n` masks, where `damageSum[mask]` is the sum of damages of enemies in the set represented by `mask`.
- Initialize a `dp` array of size `2^n` with a large value, and set `dp[0] = 0`.
- Iterate through masks from 1 to `(1 << n) - 1`.
- For each `mask`, iterate through each enemy `k` from 0 to `n-1`.
- If enemy `k` is in the current `mask`:
  - Let `prev_mask = mask ^ (1 << k)`.
  - The damage incurred to defeat `k` after `prev_mask` is `t_k * (total_initial_dps - damageSum[prev_mask])`.
  - Update `dp[mask]` with the minimum of its current value and `dp[prev_mask]` plus the damage to kill `k`.
- The final answer is `dp[(1 << n) - 1]`.

## Greedy Approach by Sorting
The most efficient solution is a greedy one. The intuition is that to minimize total damage, we should prioritize defeating enemies that are the 'most threatening'. An enemy's threat level can be quantified by the ratio of the damage it deals per second to the time it takes for us to defeat it (`damage / time_to_kill`). By always targeting the enemy with the highest ratio, we reduce the overall incoming damage most effectively over time.
**Time:** O(n log n) - This is dominated by the sorting step. Calculating the times to kill and the final total damage both take O(n) time. · **Space:** O(n) - To store the array of enemy objects or pairs for sorting.
**Pros:** Highly efficient with a polynomial time complexity, which passes the given constraints.; Relatively simple to implement once the greedy criterion is established.
**Cons:** The correctness of the greedy choice is not immediately obvious and relies on a proof (like an exchange argument), which can be subtle.
### Explanation
This approach is based on a greedy strategy. The key insight comes from an exchange argument. If we consider any two adjacent enemies, A and B, in the defeat sequence, we can analyze how the total damage changes if we swap their order. This analysis reveals that placing the enemy with a higher `damage[i] / time_to_kill[i]` ratio first always results in a lower or equal total damage. This local optimality can be extended to prove that the global optimal strategy is to sort all enemies in descending order based on this ratio.

The algorithm is as follows:
1.  For each enemy `i`, calculate the time required to defeat it: `t_i = (health[i] + power - 1) / power`.
2.  Create a structure or pair for each enemy to hold its `damage[i]` and calculated `t_i`.
3.  Sort these enemies in descending order based on the ratio `damage[i] / t_i`. To avoid floating-point precision issues, the comparison `d1/t1 > d2/t2` is rewritten as `d1 * t2 > d2 * t1`. It's important to use `long` for this cross-multiplication to prevent potential integer overflow.
4.  After sorting, iterate through the sorted list of enemies to calculate the total damage. We maintain a running sum of the DPS of all currently alive enemies (`current_dps`).
5.  For each enemy in the sorted order, we add `t_i * current_dps` to the total damage, and then subtract `damage[i]` from `current_dps` as this enemy is now considered defeated.

This method is efficient and correct for this problem.

```java
import java.util.Arrays;

class Solution {
    class Enemy {
        int damage;
        long timeToKill;

        Enemy(int damage, long timeToKill) {
            this.damage = damage;
            this.timeToKill = timeToKill;
        }
    }

    public long minimumDamage(int power, int[] damage, int[] health) {
        int n = damage.length;
        Enemy[] enemies = new Enemy[n];
        long totalInitialDps = 0;

        for (int i = 0; i < n; i++) {
            long time = (long)(health[i] + power - 1) / power;
            enemies[i] = new Enemy(damage[i], time);
            totalInitialDps += damage[i];
        }

        // Sort enemies in descending order of damage/time ratio.
        // To avoid floating point, we compare d1/t1 > d2/t2 as d1*t2 > d2*t1.
        // Use long for multiplication to avoid overflow.
        Arrays.sort(enemies, (e1, e2) -> {
            long val1 = (long)e1.damage * e2.timeToKill;
            long val2 = (long)e2.damage * e1.timeToKill;
            return Long.compare(val2, val1); // Descending order
        });

        long totalDamageDealt = 0;
        long currentDps = totalInitialDps;

        for (Enemy enemy : enemies) {
            totalDamageDealt += enemy.timeToKill * currentDps;
            currentDps -= enemy.damage;
        }

        return totalDamageDealt;
    }
}
```
### Algorithm
- Create a structure or class, say `Enemy`, to store each enemy's `damage` and its calculated `timeToKill`.
- For each enemy `i`, calculate `timeToKill[i] = (health[i] + power - 1) / power`.
- Populate an array of `Enemy` objects.
- Sort the `Enemy` array in descending order based on the ratio `damage / timeToKill`. To avoid floating-point arithmetic and potential precision errors, the comparison `d1/t1 > d2/t2` should be implemented as `d1 * t2 > d2 * t1`. Use `long` for the cross-multiplication to prevent overflow.
- Initialize `total_damage = 0` and `current_dps = sum of all damages`.
- Iterate through the sorted `Enemy` array:
  - For the current enemy `e`:
    - Add damage for this step: `total_damage += e.timeToKill * current_dps`.
    - Decrease the dps for subsequent steps: `current_dps -= e.damage`.
- Return `total_damage`.