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