Minimum Time to Kill All Monsters - Practice Coding Problems

Minimum Time to Kill All Monsters - Problem

You are given an integer array power where power[i] is the power of the i^th 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
The value of gain increases by 1

Return the minimum number of days needed to defeat all the monsters.

Input & Output

Example 1 — Basic Case

$ Input: power = [3,1,4]

› Output: 7

💡 Note: Optimal order [4,3,1]: Day 1-4 build mana to defeat monster with power 4 (gain becomes 2), Day 5-6 build mana to defeat monster with power 3 (gain becomes 3), Day 7 defeat monster with power 1. Total: 7 days.

Example 2 — Small Array

$ Input: power = [1,1,4]

› Output: 4

💡 Note: Optimal order [1,1,4]: Day 1 defeat first monster (gain=2), Day 2 defeat second monster (gain=3), Day 3-4 build mana to defeat monster with power 4. Total: 4 days.

Example 3 — Single Monster

$ Input: power = [2]

› Output: 2

💡 Note: Only one monster with power 2. Need 2 days to build enough mana (gain=1 each day). Total: 2 days.

Constraints

1 ≤ power.length ≤ 17
1 ≤ power[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of monster powers: [3,1,4]

Process

Try different defeat orders, mana resets after each kill

Output

Minimum days needed: 7

Key Takeaway

🎯 Key Insight: Order matters! Defeating stronger monsters first can be optimal when it saves more days overall.

Asked in

G Google 45 a Amazon 38 M Microsoft 32

The key insight is that the order of defeating monsters matters significantly - defeating weaker monsters first increases your daily mana gain, making stronger monsters easier to defeat later. Best approach is Dynamic Programming with Bitmask to try all orders efficiently. Time: O(2ⁿ × n), Space: O(2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DP with State Pruning	O(2ⁿ × n)	O(2ⁿ)	Enhanced DP with better state transitions and pruning techniques
Brute Force Recursion	O(n! × n²)	O(n)	Try all possible orders of defeating monsters recursively
Dynamic Programming with Bitmask	O(2ⁿ × n²)	O(2ⁿ)	Use memoization with bitmask to avoid recalculating same states

Optimized DP with State Pruning — Algorithm Steps

Use compact state representation
Implement early pruning for suboptimal paths
Optimize transition calculations
Use iterative DP instead of recursion when possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize States

Start with empty state, all others infinite

Process Each State

For each reachable state, try adding each monster

Update Minimum

Keep best path to each state configuration

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int popcount(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int solution(int* power, int n) {
    int* dp = malloc((1 << n) * sizeof(int));
    for (int i = 0; i < (1 << n); i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == INT_MAX) continue;
        
        int gain = popcount(mask) + 1;
        
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                int newMask = mask | (1 << i);
                int daysNeeded = (power[i] + gain - 1) / gain;
                if (dp[mask] + daysNeeded < dp[newMask]) {
                    dp[newMask] = dp[mask] + daysNeeded;
                }
            }
        }
    }
    
    int result = dp[(1 << n) - 1];
    free(dp);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int power[20], n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        power[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(power, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2ⁿ states with optimized O(n) transitions per state

✓ Linear Growth

Space Complexity

O(2ⁿ)

DP table stores one value per bitmask state

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DP with State Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler