Minimum time to kill all monsters

Array Dynamic Programming Bit Manipulation Bitmask

57.4% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(power: Vec<i32>) -> i64 {
    let n = power.len();
    let full = 1usize << n;
    let mut dp = vec![i64::MAX; full];
    dp[0] = 0;
    for mask in 0..full {
      if dp[mask] == i64::MAX { continue; }
      let gain = (mask.count_ones() + 1) as i64;
      for i in 0..n {
        if mask & (1 << i) != 0 { continue; }
        let next = mask | (1 << i);
        let days = (power[i] as i64 + gain - 1) / gain;
        dp[next] = dp[next].min(dp[mask] + days);
      }
    }
    dp[full - 1]
  }
}