Minimum Time to Break Locks II - Practice Coding Problems

Minimum Time to Break Locks II - Problem

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 ith 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 ith 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 1

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]

› Output: 5

💡 Note: Optimal order is [1, 3, 4]: Factor 1 breaks lock with strength 1 in 1 minute, factor 2 breaks lock with strength 3 in 2 minutes (ceil(3/2)), factor 3 breaks lock with strength 4 in 2 minutes (ceil(4/3)). Total: 1 + 2 + 2 = 5 minutes.

Example 2 — Equal Strengths

$ Input: strength = [2, 2, 2]

› Output: 6

💡 Note: All locks have equal strength, so order doesn't matter: Factor 1 takes ceil(2/1)=2 minutes, factor 2 takes ceil(2/2)=1 minute, factor 3 takes ceil(2/3)=1 minute. Total: 2 + 1 + 1 = 4 minutes.

Example 3 — Single Lock

$ Input: strength = [5]

› Output: 5

💡 Note: Only one lock with strength 5. Factor starts at 1, so it takes ceil(5/1) = 5 minutes to break.

Constraints

1 ≤ strength.length ≤ 8
1 ≤ strength[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of lock strengths: [3, 4, 1]

Process

Find optimal order considering increasing sword factor

Output

Minimum total time: 5 minutes

Key Takeaway

🎯 Key Insight: Breaking locks in optimal order (considering increasing sword factor) minimizes total time

Asked in

a Amazon 15 G Google 12 M Microsoft 8

This problem requires finding the optimal order to break locks with an evolving sword. The key insight is that the sword factor increases after each lock, so breaking easier locks early may save time overall. For small inputs (n ≤ 8), dynamic programming with bitmask provides the best balance of efficiency and correctness. Time: O(2^n × n²), Space: O(2^n × n).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(n!)	O(n)	Use DFS with pruning to avoid exploring all permutations when partial solutions exceed current best
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible orders of breaking locks and find the minimum time
Dynamic Programming with Bitmask	O(2^n × n²)	O(2^n × n)	Use bitmask DP to store states of which locks are broken and avoid redundant calculations

Backtracking with Pruning — Algorithm Steps

Start DFS with empty lock sequence and factor = 1
For each unused lock, calculate time to break it
If partial time exceeds current best, prune this branch
Continue recursively until all locks are assigned
Track minimum time across all complete solutions

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin with no locks broken, factor = 1

Explore & Prune

Try each unused lock, prune if partial time exceeds current best

Update Best

When all locks broken, update minimum time if better

Code -

solution.c — C

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

int minTime;

void backtrack(int* strength, bool* used, int n, int currentTime, int factor, int locksUsed) {
    if (locksUsed == n) {
        if (currentTime < minTime) {
            minTime = currentTime;
        }
        return;
    }
    
    // Pruning
    if (currentTime >= minTime) {
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            int timeForLock = (int)ceil((double)strength[i] / factor);
            used[i] = true;
            backtrack(strength, used, n, currentTime + timeForLock, factor + 1, locksUsed + 1);
            used[i] = false;
        }
    }
}

int solution(int* strength, int n) {
    minTime = INT_MAX;
    bool* used = (bool*)calloc(n, sizeof(bool));
    
    backtrack(strength, used, n, 0, 1, 0);
    
    free(used);
    return minTime;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple JSON array parsing
    int strength[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        strength[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(strength, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

In worst case still explores all permutations, but pruning reduces average case significantly

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth is n, plus arrays to track used locks

⚡ Linearithmic Space

29.4K 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

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler