##### 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 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

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

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