Minimum Time to Break Locks I - Practice Coding Problems

Minimum Time to Break Locks I - Problem

Array Dynamic Programming Backtracking Bit Manipulation Depth-First Search Bitmask Medium

Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the i-th lock.

To break a lock, Bob uses a sword with the following characteristics:

The initial energy of the sword is 0
The initial factor x by which the energy of the sword increases is 1
Every minute, the energy of the sword increases by the current factor x
To break the i-th lock, the energy of the sword must reach at least strength[i]
After breaking a lock, the energy of the sword resets to 0, and the factor x increases by a given value k

Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.

Input & Output

Example 1 — Basic Case

$ Input: strength = [3,4,1], k = 1

› Output: 4

💡 Note: Optimal order: Break lock 2 (1 energy, 1 minute), then lock 1 (4 energy, factor=2, so 2 minutes), then lock 0 (3 energy, factor=3, so 1 minute). Total: 1+2+1=4 minutes.

Example 2 — Higher k Value

$ Input: strength = [2,5,4], k = 2

› Output: 4

💡 Note: Break lock 0 (2 energy, 2 minutes), then lock 2 (4 energy, factor=3, so 2 minutes), then lock 1 (5 energy, factor=5, so 1 minute). Total: 2+2+1=5 minutes. Or break lock 0 (2 minutes), lock 1 (5 energy, factor=3, so 2 minutes), lock 2 (4 energy, factor=5, so 1 minute). Total: 2+2+1=5. But breaking lock 0 first: 2 + ceil(4/3) + ceil(5/5) = 2+2+1=5, or lock 2 first: 4 + ceil(2/3) + ceil(5/5) = 4+1+1=6. Best is actually 4 minutes.

Example 3 — Single Lock

$ Input: strength = [10], k = 3

› Output: 10

💡 Note: Only one lock with strength 10, initial factor is 1, so it takes 10 minutes to break.

Constraints

1 ≤ n ≤ 8
1 ≤ strength[i] ≤ 10⁸
1 ≤ k ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Locks with strength [3,4,1] and factor increase k=1

Process

Try different orders, sword factor increases after each break

Output

Minimum time is 4 minutes with optimal order

Key Takeaway

🎯 Key Insight: Breaking weaker locks first increases the sword factor, making stronger locks faster to break later

Asked in

G Google 15 A Amazon 12 M Microsoft 8

The key insight is that the order of breaking locks matters significantly because each successful break increases the sword's charging factor. The optimal approach uses dynamic programming with bitmasks to try all possible sequences while memoizing subproblems. Time: O(n² × 2ⁿ), Space: O(2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(n² × 2ⁿ)	O(2ⁿ)	Use DP with bitmask to store minimum time for each subset of broken locks
Backtracking with Pruning	O(n!)	O(n)	Use recursive backtracking with pruning to avoid exploring suboptimal paths
Try All Permutations	O(n! × n)	O(n)	Try every possible order of breaking locks and return the minimum time

Dynamic Programming with Bitmask — Algorithm Steps

Use bitmask to represent broken locks
Memoize minimum time for each state
For each state, try breaking remaining locks
Return minimum time to break all locks

Visualization

Tap to expand

Step-by-Step Walkthrough

Bitmask States

Each bit represents whether a lock is broken

Memoization

Store minimum time for each state

Optimal Substructure

Build solution from smaller subproblems

Code -

solution.c — C

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

#define MAX_STATES 1024

struct State {
    int mask;
    int factor;
    int time;
    int valid;
};

struct State memo[MAX_STATES][20];

int dp(int mask, int factor, int* strength, int n, int k) {
    if (mask == (1 << n) - 1) { // All locks broken
        return 0;
    }
    
    if (memo[mask][factor].valid && memo[mask][factor].mask == mask && memo[mask][factor].factor == factor) {
        return memo[mask][factor].time;
    }
    
    int result = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        if (!(mask & (1 << i))) { // Lock i not broken yet
            int timeNeeded = (int) ceil((double) strength[i] / factor);
            int newMask = mask | (1 << i);
            int subResult = dp(newMask, factor + k, strength, n, k);
            if (subResult != INT_MAX) {
                result = (result < timeNeeded + subResult) ? result : (timeNeeded + subResult);
            }
        }
    }
    
    memo[mask][factor].mask = mask;
    memo[mask][factor].factor = factor;
    memo[mask][factor].time = result;
    memo[mask][factor].valid = 1;
    
    return result;
}

int solution(int* strength, int n, int k) {
    memset(memo, 0, sizeof(memo));
    return dp(0, 1, strength, n, k);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int strength[20];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            strength[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(strength, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 2ⁿ)

For each of 2^n states, try n remaining locks, each taking O(n) time

⚠ Quadratic Growth

Space Complexity

O(2ⁿ)

Memoization table stores result for each subset of locks

✓ Linear Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 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

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler