# 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 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 + Memorization Search or Dynamic Programming

Since defeating monsters can increase the daily magic power gain $gain$, the order of defeating monsters affects the result, so we need to enumerate. Noting that the data range of the problem is small, we consider using state compression dynamic programming to solve it.

We define a state $mask$ to represent the current situation of defeating monsters. In its binary representation, $1$ represents the monsters that have been defeated, and $0$ represents the monsters that have not been defeated.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(2^n)$. Here, $n$ is the number of monsters.

• 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);
}

}
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));
}
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);
}

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));
}
return ans;
}
};

• class Solution:
def minimumTime(self, power: List[int]) -> int:
@cache
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
}
dfs = func(mask int) int64 {
}
if cnt == n {
return 0
}
var ans int64 = math.MaxInt64
for i, v := range power {
if (mask >> i & 1) == 1 {
continue
}
}
return ans
}
return dfs(0)
}

• function minimumTime(power: number[]): number {
const n = power.length;
const f = new Array(1 << n).fill(-1);
}
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)));
}
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;
}