3273. Minimum Amount of Damage Dealt to Bob LeetCode Solution
In this guide, you will get 3273. Minimum Amount of Damage Dealt to Bob LeetCode Solution with the best time and space complexity. The solution to Minimum Amount of Damage Dealt to Bob problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Amount of Damage Dealt to Bob
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.
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
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
3273. Minimum Amount of Damage Dealt to Bob LeetCode Solution in C++
struct Enemy {
int damage;
int timeTakenDown;
};
class Solution {
public:
long long minDamage(int power, vector<int>& damage, vector<int>& health) {
long ans = 0;
long sumDamage = accumulate(damage.begin(), damage.end(), 0L);
vector<Enemy> enemies;
for (int i = 0; i < damage.size(); ++i)
enemies.emplace_back(damage[i], (health[i] + power - 1) / power);
// It's better to take down the enemy i first if the damage dealt of taking
// down i first is less than the damage dealt of taking down j first. So,
// damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
// damage[j] * t[j] + (t[i] + t[j]) * damage[i]
// => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
// damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
// => damage[j] * t[i] < damage[i] * t[j]
// => damage[j] / t[j] < damage[i] / t[i]
ranges::sort(enemies, ranges::greater{}, [](const Enemy& e) {
return static_cast<double>(e.damage) / e.timeTakenDown;
});
for (const Enemy& enemy : enemies) {
ans += sumDamage * enemy.timeTakenDown;
sumDamage -= enemy.damage;
}
return ans;
}
}; /* code provided by PROGIEZ */
3273. Minimum Amount of Damage Dealt to Bob LeetCode Solution in Java
class Enemy {
public int damage;
public int timeTakenDown;
public Enemy(int damage, int timeTakenDown) {
this.damage = damage;
this.timeTakenDown = timeTakenDown;
}
}
class Solution {
public long minDamage(int power, int[] damage, int[] health) {
long ans = 0;
long sumDamage = Arrays.stream(damage).asLongStream().sum();
Enemy[] enemies = new Enemy[damage.length];
for (int i = 0; i < damage.length; ++i)
enemies[i] = new Enemy(damage[i], (health[i] + power - 1) / power);
// It's better to take down the enemy i first if the damage dealt of taking
// down i first is less than the damage dealt of taking down j first. So,
// damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
// damage[j] * t[j] + (t[i] + t[j]) * damage[i]
// => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
// damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
// => damage[j] * t[i] < damage[i] * t[j]
// => damage[j] / t[j] < damage[i] / t[i]
Arrays.sort(enemies,
(a, b)
-> Double.compare((double) b.damage / b.timeTakenDown,
(double) a.damage / a.timeTakenDown));
for (final Enemy enemy : enemies) {
ans += sumDamage * enemy.timeTakenDown;
sumDamage -= enemy.damage;
}
return ans;
}
} // code provided by PROGIEZ
3273. Minimum Amount of Damage Dealt to Bob LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class Enemy:
damage: int
timeTakenDown: int
class Solution:
def minDamage(self, power: int, damage: list[int], health: list[int]) -> int:
ans = 0
sumDamage = sum(damage)
enemies = [Enemy(d, (h + power - 1) // power)
for d, h in zip(damage, health)]
# It's better to take down the enemy i first if the damage dealt of taking
# down i first is less than the damage dealt of taking down j first. So,
# damage[i] * t[i] + (t[i] + t[j]) * damage[j] <
# damage[j] * t[j] + (t[i] + t[j]) * damage[i]
# => damage[i] * t[i] + damage[j] * t[i] + damage[j] * t[j] <
# damage[j] * t[j] + damage[i] * t[j] + damage[i] * t[i]
# => damage[j] * t[i] < damage[i] * t[j]
# => damage[j] / t[j] < damage[i] / t[i]
enemies.sort(key=lambda x: -x.damage / x.timeTakenDown)
for enemy in enemies:
ans += sumDamage * enemy.timeTakenDown
sumDamage -= enemy.damage
return ans # code by PROGIEZ
