Hard

Minimum Time to Kill All Monsters

LAB

Given monster powers, gain starts at 1 and increases by 1 after each kill. Killing a monster of power p takes ceil(p/gain). Return the minimum total time.

EXAMPLES

Example 1

Input
{
  "power": [
    3,
    1,
    4
  ]
}

Output
5

FUNCTION SHAPE

power: intArray→int

SOLUTION NOTE

Gain increases with each kill, so order matters. Bitmask tracks killed monsters. Derive gain from popcount.

Reveal reference solution +

pythonREFERENCE

def minimumTime(self, power: List[int]) -> int:
    from math import ceil
    n = len(power)

    @cache
    def dp(mask):
        dead = bin(mask).count('1')
        gain = dead + 1
        if dead == n: return 0

        return min(ceil(power[i] / gain) + dp(mask | (1 << i))
                   for i in range(n) if not (mask & (1 << i)))

    return dp(0)

TimeO(n × 2^n)

SpaceO(2^n)

Open on LeetCode ↗