LeetCode 2403. Minimum Time to Kill All Monsters Solution in Java, C++, Python & More | Explanation + Code

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 by 1.

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

Solution 1: State Compression + Memoization Search

We note that the number of monsters is at most 17, which means we can use a 17-bit binary number to represent the state of the monsters. The i-th bit being 1 indicates that the i-th monster is still alive, and 0 indicates that the i-th monster has been defeated.

We design a function dfs(mask) to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is mask. The answer is dfs(2ⁿ - 1), where n is the number of monsters.

The calculation of the function dfs(mask) is as follows:

• If mask = 0, it means all monsters have been defeated, return 0;
• Otherwise, we enumerate each monster i. If the i-th monster is still alive, we can choose to defeat the i-th monster, then recursively calculate dfs(mask \oplus 2ⁱ), and update the answer to ans = min(ans, dfs(mask \oplus 2ⁱ) + \lceil ^x⁄_gain \rceil), where x is the strength of the i-th monster, and gain = 1 + (n - mask.bit_count()) represents the current daily mana gain.

Finally, we return dfs(2ⁿ - 1).

The time complexity is O(2ⁿ × n), and the space complexity is O(2ⁿ). Here, n is the number of monsters.

PythonJavaC++GoTypeScript

class Solution: def minimumTime(self, power: List[int]) -> int: @cache def dfs(mask: int) -> int: if mask == 0: return 0 ans = inf gain = 1 + (n - mask.bit_count()) for i, x in enumerate(power): if mask >> i & 1: ans = min(ans, dfs(mask ^ (1 << i)) + (x + gain - 1) // gain) return ans n = len(power) return dfs((1 << n) - 1)(code-box)

class Solution { private int n; private int[] power; private Long[] f; public long minimumTime(int[] power) { n = power.length; this.power = power; f = new Long[1 << n]; return dfs((1 << n) - 1); } private long dfs(int mask) { if (mask == 0) { return 0; } if (f[mask] != null) { return f[mask]; } f[mask] = Long.MAX_VALUE; int gain = 1 + (n - Integer.bitCount(mask)); for (int i = 0; i < n; ++i) { if ((mask >> i & 1) == 1) { f[mask] = Math.min(f[mask], dfs(mask ^ 1 << i) + (power[i] + gain - 1) / gain); } } return f[mask]; } }(code-box)

class Solution { public: long long minimumTime(vector<int>& power) { int n = power.size(); long long f[1 << n]; memset(f, -1, sizeof(f)); auto dfs = [&](this auto&& dfs, int mask) -> long long { if (mask == 0) { return 0; } if (f[mask] != -1) { return f[mask]; } f[mask] = LLONG_MAX; int gain = 1 + (n - __builtin_popcount(mask)); for (int i = 0; i < n; ++i) { if (mask >> i & 1) { f[mask] = min(f[mask], dfs(mask ^ (1 << i)) + (power[i] + gain - 1) / gain); } } return f[mask]; }; return dfs((1 << n) - 1); } };(code-box)

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 mask == 0 { return 0 } if f[mask] != -1 { return f[mask] } f[mask] = 1e18 gain := 1 + (n - bits.OnesCount(uint(mask))) for i, x := range power { if mask>>i&1 == 1 { f[mask] = min(f[mask], dfs(mask^(1<<i))+int64(x+gain-1)/int64(gain)) } } return f[mask] } return dfs(1<<n - 1) }(code-box)

function minimumTime(power: number[]): number { const n = power.length; const f: number[] = Array(1 << n).fill(-1); const dfs = (mask: number): number => { if (mask === 0) { return 0; } if (f[mask] !== -1) { return f[mask]; } f[mask] = Infinity; const gain = 1 + (n - bitCount(mask)); for (let i = 0; i < n; ++i) { if ((mask >> i) & 1) { f[mask] = Math.min(f[mask], dfs(mask ^ (1 << i)) + Math.ceil(power[i] / gain)); } } return f[mask]; }; return dfs((1 << n) - 1); } function bitCount(i: number): number { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }(code-box)

Solution 2: State Compression + Dynamic Programming

We can convert the memoization search in Solution 1 to dynamic programming. Define f[mask] to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is mask. Here, mask is an n-bit binary number, where the i-th bit being 1 indicates that the i-th monster has been defeated, and 0 indicates that the i-th monster is still alive. Initially, f[0] = 0, and the rest f[mask] = +∞. The answer is f[2ⁿ - 1].

We enumerate mask in the range [1, 2ⁿ - 1]. For each mask, we enumerate each monster i. If the i-th monster is defeated, it can be transferred from the previous state mask \oplus 2ⁱ, with a transfer cost of (power[i] + gain - 1) / gain, where gain = mask.bitCount().

Finally, return f[2ⁿ - 1].

The time complexity is O(2ⁿ × n), and the space complexity is O(2ⁿ). Here, n is the number of monsters.

PythonJavaC++GoTypeScript

class Solution: def minimumTime(self, power: List[int]) -> int: n = len(power) f = [inf] * (1 << n) f[0] = 0 for mask in range(1, 1 << n): gain = mask.bit_count() for i, x in enumerate(power): if mask >> i & 1: f[mask] = min(f[mask], f[mask ^ (1 << i)] + (x + gain - 1) // gain) return f[-1](code-box)

class Solution { public long minimumTime(int[] power) { int n = power.length; long[] f = new long[1 << n]; Arrays.fill(f, Long.MAX_VALUE); f[0] = 0; for (int mask = 1; mask < 1 << n; ++mask) { int gain = Integer.bitCount(mask); for (int i = 0; i < n; ++i) { if ((mask >> i & 1) == 1) { f[mask] = Math.min(f[mask], f[mask ^ 1 << i] + (power[i] + gain - 1) / gain); } } } return f[(1 << n) - 1]; } }(code-box)

class Solution { public: long long minimumTime(vector<int>& power) { int n = power.size(); long long f[1 << n]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int mask = 1; mask < 1 << n; ++mask) { int gain = __builtin_popcount(mask); for (int i = 0; i < n; ++i) { if (mask >> i & 1) { f[mask] = min(f[mask], f[mask ^ (1 << i)] + (power[i] + gain - 1) / gain); } } } return f[(1 << n) - 1]; } };(code-box)

func minimumTime(power []int) int64 { n := len(power) f := make([]int64, 1<<n) for i := range f { f[i] = 1e18 } f[0] = 0 for mask := 1; mask < 1<<n; mask++ { gain := bits.OnesCount(uint(mask)) for i, x := range power { if mask>>i&1 == 1 { f[mask] = min(f[mask], f[mask^(1<<i)]+int64(x+gain-1)/int64(gain)) } } } return f[1<<n-1] }(code-box)

function minimumTime(power: number[]): number { const n = power.length; const f: number[] = Array(1 << n).fill(Infinity); f[0] = 0; for (let mask = 1; mask < 1 << n; ++mask) { const gain = bitCount(mask); for (let i = 0; i < n; ++i) { if ((mask >> i) & 1) { f[mask] = Math.min(f[mask], f[mask ^ (1 << i)] + Math.ceil(power[i] / gain)); } } } return f.at(-1)!; } function bitCount(i: number): number { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }(code-box)