Problem

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 theminimum number of days needed to defeat all the monsters.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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] <= 10^9

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

Since the number of monsters is small (<= 17), we can use bitmask DP to try all possible orders of killing monsters. For each state, we track the minimum days needed and the current gain value. The key is to choose the next monster to kill such that the required mana can be accumulated in the fewest days.

Approach

  1. Let n = number of monsters.
  2. Use dp[mask][gain]: minimum days to kill monsters in mask with current gain.
  3. For each mask, try killing each remaining monster:
    • Calculate days needed to accumulate enough mana.
    • Update dp for the new mask and increased gain.
  4. Use memoization to avoid recomputation.
  5. The answer is the minimum days to kill all monsters.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int minimumTime(vector<int>& power) {
        int n = power.size();
        vector<vector<int>> dp(1<<n, vector<int>(n+1, INT_MAX));
        dp[0][1] = 0;
        for (int mask = 0; mask < (1<<n); ++mask) {
            for (int gain = 1; gain <= n; ++gain) {
                if (dp[mask][gain] == INT_MAX) continue;
                for (int i = 0; i < n; ++i) {
                    if (!(mask & (1<<i))) {
                        int mana = 0, days = 0;
                        while (mana < power[i]) {
                            mana += gain;
                            days++;
                        }
                        int nmask = mask | (1<<i);
                        if (dp[nmask][gain+1] > dp[mask][gain] + days)
                            dp[nmask][gain+1] = dp[mask][gain] + days;
                    }
                }
            }
        }
        int ans = INT_MAX;
        for (int gain = 1; gain <= n; ++gain)
            ans = min(ans, dp[(1<<n)-1][gain]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func minimumTime(power []int) int {
    n := len(power)
    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n+2)
        for j := range dp[i] {
            dp[i][j] = 1<<30
        }
    }
    dp[0][1] = 0
    for mask := 0; mask < 1<<n; mask++ {
        for gain := 1; gain <= n; gain++ {
            if dp[mask][gain] == 1<<30 {
                continue
            }
            for i := 0; i < n; i++ {
                if mask&(1<<i) == 0 {
                    mana, days := 0, 0
                    for mana < power[i] {
                        mana += gain
                        days++
                    }
                    nmask := mask | (1 << i)
                    if dp[nmask][gain+1] > dp[mask][gain]+days {
                        dp[nmask][gain+1] = dp[mask][gain]+days
                    }
                }
            }
        }
    }
    ans := 1<<30
    for gain := 1; gain <= n; gain++ {
        if dp[(1<<n)-1][gain] < ans {
            ans = dp[(1<<n)-1][gain]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int minimumTime(int[] power) {
        int n = power.length;
        int[][] dp = new int[1<<n][n+2];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][1] = 0;
        for (int mask = 0; mask < (1<<n); mask++) {
            for (int gain = 1; gain <= n; gain++) {
                if (dp[mask][gain] == Integer.MAX_VALUE) continue;
                for (int i = 0; i < n; i++) {
                    if ((mask & (1<<i)) == 0) {
                        int mana = 0, days = 0;
                        while (mana < power[i]) {
                            mana += gain;
                            days++;
                        }
                        int nmask = mask | (1<<i);
                        if (dp[nmask][gain+1] > dp[mask][gain] + days)
                            dp[nmask][gain+1] = dp[mask][gain] + days;
                    }
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int gain = 1; gain <= n; gain++)
            ans = Math.min(ans, dp[(1<<n)-1][gain]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun minimumTime(power: IntArray): Int {
        val n = power.size
        val dp = Array(1 shl n) { IntArray(n+2) { Int.MAX_VALUE } }
        dp[0][1] = 0
        for (mask in 0 until (1 shl n)) {
            for (gain in 1..n) {
                if (dp[mask][gain] == Int.MAX_VALUE) continue
                for (i in 0 until n) {
                    if (mask and (1 shl i) == 0) {
                        var mana = 0
                        var days = 0
                        while (mana < power[i]) {
                            mana += gain
                            days++
                        }
                        val nmask = mask or (1 shl i)
                        if (dp[nmask][gain+1] > dp[mask][gain] + days)
                            dp[nmask][gain+1] = dp[mask][gain] + days
                    }
                }
            }
        }
        var ans = Int.MAX_VALUE
        for (gain in 1..n) {
            ans = minOf(ans, dp[(1 shl n)-1][gain])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumTime(self, power: list[int]) -> int:
        n: int = len(power)
        dp = [[float('inf')] * (n+2) for _ in range(1<<n)]
        dp[0][1] = 0
        for mask in range(1<<n):
            for gain in range(1, n+1):
                if dp[mask][gain] == float('inf'):
                    continue
                for i in range(n):
                    if not (mask & (1<<i)):
                        mana, days = 0, 0
                        while mana < power[i]:
                            mana += gain
                            days += 1
                        nmask = mask | (1<<i)
                        if dp[nmask][gain+1] > dp[mask][gain] + days:
                            dp[nmask][gain+1] = dp[mask][gain] + days
        ans = float('inf')
        for gain in range(1, n+1):
            ans = min(ans, dp[(1<<n)-1][gain])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn minimum_time(power: Vec<i32>) -> i32 {
        let n = power.len();
        let mut dp = vec![vec![i32::MAX; n+2]; 1<<n];
        dp[0][1] = 0;
        for mask in 0..(1<<n) {
            for gain in 1..=n {
                if dp[mask][gain] == i32::MAX { continue; }
                for i in 0..n {
                    if (mask & (1<<i)) == 0 {
                        let mut mana = 0;
                        let mut days = 0;
                        while mana < power[i] {
                            mana += gain as i32;
                            days += 1;
                        }
                        let nmask = mask | (1<<i);
                        if dp[nmask][gain+1] > dp[mask][gain] + days {
                            dp[nmask][gain+1] = dp[mask][gain] + days;
                        }
                    }
                }
            }
        }
        let mut ans = i32::MAX;
        for gain in 1..=n {
            ans = ans.min(dp[(1<<n)-1][gain]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    minimumTime(power: number[]): number {
        const n = power.length;
        const dp = Array(1<<n).fill(0).map(() => Array(n+2).fill(Infinity));
        dp[0][1] = 0;
        for (let mask = 0; mask < (1<<n); mask++) {
            for (let gain = 1; gain <= n; gain++) {
                if (dp[mask][gain] === Infinity) continue;
                for (let i = 0; i < n; i++) {
                    if ((mask & (1<<i)) === 0) {
                        let mana = 0, days = 0;
                        while (mana < power[i]) {
                            mana += gain;
                            days++;
                        }
                        const nmask = mask | (1<<i);
                        if (dp[nmask][gain+1] > dp[mask][gain] + days)
                            dp[nmask][gain+1] = dp[mask][gain] + days;
                    }
                }
            }
        }
        let ans = Infinity;
        for (let gain = 1; gain <= n; gain++)
            ans = Math.min(ans, dp[(1<<n)-1][gain]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n), since for each mask and gain, we try all monsters.
  • 🧺 Space complexity: O(n * 2^n), for the DP table.