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

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

All Problems

All Solutions