Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2403.html
2403. Minimum Time to Kill All Monsters
Description
You are given an integer array power
where power[i]
is the power of the ith
monster.
You start with 0
mana points, and each day you increase your mana points by gain
where gain
initially is equal to 1
.
Each day, after gaining gain
mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:
- your mana points will be reset to
0
, and - the value of
gain
increases by1
.
Return the minimum number of days needed to defeat all the monsters.
Example 1:
Input: power = [3,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. - Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. - Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster. It can be proven that 4 is the minimum number of days needed.
Example 2:
Input: power = [1,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 4 is the minimum number of days needed.
Example 3:
Input: power = [1,2,4,9] Output: 6 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. - Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster. - Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 6 is the minimum number of days needed.
Constraints:
1 <= power.length <= 17
1 <= power[i] <= 109
Solutions
-
class Solution { private int n; private long[] f; private int[] power; public long minimumTime(int[] power) { n = power.length; f = new long[1 << n]; Arrays.fill(f, -1); this.power = power; return dfs(0); } private long dfs(int mask) { if (f[mask] != -1) { return f[mask]; } int cnt = Integer.bitCount(mask); if (cnt == n) { return 0; } long ans = Long.MAX_VALUE; for (int i = 0; i < n; ++i) { if (((mask >> i) & 1) == 1) { continue; } ans = Math.min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1)); } f[mask] = ans; return ans; } }
-
using ll = long long; class Solution { public: vector<ll> f; vector<int> power; int n; long long minimumTime(vector<int>& power) { n = power.size(); f.assign(1 << n, -1); this->power = power; return dfs(0); } ll dfs(int mask) { if (f[mask] != -1) return f[mask]; int cnt = __builtin_popcount(mask); if (cnt == n) return 0; ll ans = LONG_MAX; for (int i = 0; i < n; ++i) { if ((mask >> i) & 1) continue; ans = min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1)); } f[mask] = ans; return ans; } };
-
class Solution: def minimumTime(self, power: List[int]) -> int: @cache def dfs(mask): cnt = mask.bit_count() if cnt == len(power): return 0 ans = inf for i, v in enumerate(power): if mask & (1 << i): continue ans = min(ans, dfs(mask | 1 << i) + (v + cnt) // (cnt + 1)) return ans return dfs(0)
-
func minimumTime(power []int) int64 { n := len(power) f := make([]int64, 1<<n) for i := range f { f[i] = -1 } var dfs func(mask int) int64 dfs = func(mask int) int64 { if f[mask] != -1 { return f[mask] } cnt := bits.OnesCount(uint(mask)) if cnt == n { return 0 } var ans int64 = math.MaxInt64 for i, v := range power { if (mask >> i & 1) == 1 { continue } ans = min(ans, dfs(mask|1<<i)+int64((v+cnt)/(cnt+1))) } f[mask] = ans return ans } return dfs(0) } func min(a, b int64) int64 { if a < b { return a } return b }
-
function minimumTime(power: number[]): number { const n = power.length; const f = new Array(1 << n).fill(-1); function dfs(mask) { if (f[mask] != -1) { return f[mask]; } const cnt = bitCount(mask); if (cnt == n) { return 0; } let ans = Infinity; for (let i = 0; i < n; ++i) { if ((mask >> i) & 1) { continue; } ans = Math.min( ans, dfs(mask | (1 << i)) + Math.ceil(power[i] / (cnt + 1)), ); } f[mask] = ans; return ans; } return dfs(0); } function bitCount(x) { let cnt = 0; for (let i = 0; i < 32; ++i) { if ((x >> i) & 1) { ++cnt; } } return cnt; }