Skip to content

Practice Minimum Amount of Damage Dealt to Bob

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3273
LeetCode Problem

Minimum Amount of Damage Dealt to Bob

Problem Statement

Every living enemy i deals damage[i] to Bob once per second. After receiving that second's damage, Bob hits one living enemy for power health points. An enemy stops attacking only after its health reaches zero or less. Find the least total damage Bob can receive before defeating every enemy. Approach: Enemy i requires hits[i]=ceil(health[i]/power) attacks. Finish enemies in increasing hits[i]/damage[i] order. Compare two enemies using cross-products rather than floating point: i goes first when hits[i]*damage[j] <= hits[j]*damage[i]. This ordering follows by comparing the damage caused by swapping two consecutive enemies. While processing the order, add hits[i] times the total damage rate of all still-living enemies, then remove damage[i]. Time: O(n log n). Use wide integers for accumulated damage. Worked example: With power 3, the first enemy below needs three hits. Defeating it first costs 3*5+1=16 damage; reversing the order costs 5+3*4=17.

Source: Minimum Amount of Damage Dealt to Bob on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
power = 3, damage = [4,1], health = [7,3]
Output
16

# Example 2

Input
power = 2, damage = [3], health = [5]
Output
9

Constraints

power is an integer from 1 through 10,000.
damage and health have the same length, from 1 through 100,000.
Each enemy damage and health value is between 1 and 10,000.

How to solve Minimum Amount of Damage Dealt to Bob

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Bob should focus on one enemy at a time, so only the order matters. Swapping two adjacent enemies changes the total by an amount depending only on those two, which forces sorting by hits needed divided by damage per second, smallest first.

Why brute force is not enough

Trying every kill order is factorial in the number of enemies, and simulating one order second by second costs the total hit count (up to 10^5 enemies times 10^4 hits) with a damage sum each second, far too slow for 100,000 enemies.

Approach

  1. For each enemy compute the attacks it survives: health divided by power, rounded up. Attacks are never wasted, so an enemy dies exactly after that many seconds of attention.
  2. Exchange argument: if enemy i is finished right before enemy j, putting i first costs hits of i times damage of j extra, while the reverse costs hits of j times damage of i extra. The smaller product goes first, and since this is a ratio ordering, sorting by hits divided by damage ascending is globally optimal.
  3. Compare with cross multiplication, hits of i times damage of j against hits of j times damage of i, so floating point rounding cannot misorder close ratios.
  4. Start with the total damage per second of all enemies. Walk the sorted order; add each enemy's hit count times the current living rate, then subtract its damage from the rate.
  5. The invariant is that the accumulated total equals all damage taken through the current enemy's death and the rate equals the damage of enemies still alive.

Walkthrough of Example 1

power = 3, damage = [4,1], health = [7,3] → 16

  1. power is 3, damage is [4,1], health is [7,3]. Enemy 0 needs ceil(7/3) = 3 hits; enemy 1 needs ceil(3/3) = 1 hit.
  2. Compare: 3 times 1 = 3 for enemy 0 first versus 1 times 4 = 4 for enemy 1 first, so enemy 0 goes first.
  3. The living rate starts at 4 + 1 = 5. Killing enemy 0 takes 3 seconds and costs 3 times 5 = 15; the rate drops to 1.
  4. Killing enemy 1 takes 1 second at rate 1, adding 1. The total 15 + 1 = 16 matches the expected output.

Time and space

Time O(n log n) · Space O(n). With n enemies, hit counts are linear and the sort dominates; an index array for sorting is linear extra memory.

Interview pitfalls

  • Using integer division instead of a ceiling for hit counts, undercounting when health is not a multiple of power.
  • Sorting by damage alone or hits alone; only the ratio works.
  • Comparing ratios as doubles; distinct ratios can round equal, so cross multiply in 64-bit integers.
  • Overflowing a 32-bit accumulator: total hits can reach 10^9 and the rate 10^9, so the answer needs 64 bits.
  • Forgetting that the enemy being attacked still deals damage every second it lives, including the second it dies.

Follow-up questions interviewers ask

  • How does the strategy change if Bob can split his power across several enemies in one second?
  • What if enemies regenerate health each second; does a simple ordering still exist?
  • Can you output the kill order and show that ties in the ratio can be broken arbitrarily?

Further reading on the technique: Greedy algorithm

Related LeetCode Problems

Practice more problems similar to Minimum Amount of Damage Dealt to Bob.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.