# Minimum Time to Break Locks I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-break-locks-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-break-locks-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array
**Companies:** [IVP](https://scaleengineer.com/companies/ivp)
---
## 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 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.

Return the **minimum** time required for Bob to break all `n` locks.

**Example 1:**

**Input:** strength = \[3,4,1\], k = 1

**Output:** 4

**Explanation:**

| Time | Energy | x | Action         | Updated x |
| ---- | ------ | - | -------------- | --------- |
| 0    | 0      | 1 | Nothing        | 1         |
| 1    | 1      | 1 | Break 3rd Lock | 2         |
| 2    | 2      | 2 | Nothing        | 2         |
| 3    | 4      | 2 | Break 2nd Lock | 3         |
| 4    | 3      | 3 | Break 1st Lock | 3         |

The locks cannot be broken in less than 4 minutes; thus, the answer is 4.

**Example 2:**

**Input:** strength = \[2,5,4\], k = 2

**Output:** 5

**Explanation:**

| Time | Energy | x | Action         | Updated x |
| ---- | ------ | - | -------------- | --------- |
| 0    | 0      | 1 | Nothing        | 1         |
| 1    | 1      | 1 | Nothing        | 1         |
| 2    | 2      | 1 | Break 1st Lock | 3         |
| 3    | 3      | 3 | Nothing        | 3         |
| 4    | 6      | 3 | Break 2nd Lock | 5         |
| 5    | 5      | 5 | Break 3rd Lock | 7         |

The locks cannot be broken in less than 5 minutes; thus, the answer is 5.

**Constraints:**

* `n == strength.length`
* `1 <= n <= 8`
* `1 <= K <= 10`
* `1 <= strength[i] <= 106`

# Approaches
## Brute Force with Permutations
This approach explores every possible order of breaking the locks. Since the total time depends on the sequence in which the locks are broken, we can generate all permutations of the locks, calculate the total time for each permutation, and find the minimum among them. Given the small constraint on `n` (up to 8), this method is feasible, although inefficient.
**Time:** O(n * n!) - There are `n!` possible permutations of the locks. Generating all permutations using the standard recursive algorithm takes `O(n * n!)` time. For each complete permutation, we spend `O(n)` time to calculate the total time. · **Space:** O(n) - This space is used for the recursion stack, which can go up to `n` levels deep, and for storing the list representing the current permutation.
**Pros:** Conceptually simple and directly models the problem statement.; Easy to implement using standard recursion and backtracking.
**Cons:** Highly inefficient due to its factorial time complexity.; Becomes infeasible for values of `n` larger than 10-12.
### Explanation
The core idea is to recognize that any sequence of breaking `n` locks corresponds to a permutation of the lock indices `{0, 1, ..., n-1}`. We can use a recursive backtracking algorithm to generate all `n!` permutations of the lock strengths. For each permutation, we simulate the process of breaking the locks in that specific order. The factor `x` starts at 1. For the `i`-th lock in the sequence (1-indexed), the factor will be `1 + (i-1) * k`. The time to break a lock with strength `s` and current factor `x` is `ceil(s / x)`. We sum up the times for all `n` locks for a given permutation and keep track of the minimum total time found so far. After checking all `n!` permutations, this minimum value is the solution.

```java
class Solution {
    long minTime = Long.MAX_VALUE;
    int k;
    int n;

    public int minimumTime(int[] strength, int k) {
        this.k = k;
        this.n = strength.length;
        java.util.List<Integer> strengthList = new java.util.ArrayList<>();
        for (int s : strength) {
            strengthList.add(s);
        }
        generatePermutations(0, strengthList);
        return (int) minTime;
    }

    private void generatePermutations(int index, java.util.List<Integer> currentPermutation) {
        if (index == n) {
            calculateTime(currentPermutation);
            return;
        }

        for (int i = index; i < n; i++) {
            java.util.Collections.swap(currentPermutation, index, i);
            generatePermutations(index + 1, currentPermutation);
            java.util.Collections.swap(currentPermutation, index, i); // backtrack
        }
    }

    private void calculateTime(java.util.List<Integer> permutation) {
        long currentTime = 0;
        long factor = 1;
        for (int s : permutation) {
            // time = ceil(s / factor)
            long time = (s + factor - 1) / factor;
            currentTime += time;
            factor += k;
        }
        minTime = Math.min(minTime, currentTime);
    }
}
```
### Algorithm
1. Initialize `minTime` to a very large value.
2. Create a list of lock strengths from the input array.
3. Implement a recursive function, say `generatePermutations(index, currentPermutation)`, to explore all possible orderings of locks.
4. The base case for the recursion is when `index` reaches the number of locks `n`. This signifies that a complete permutation has been formed.
5. In the base case, calculate the total time for the `currentPermutation`:
    a. Initialize `totalTime = 0` and `factor = 1`.
    b. Iterate through the locks in the `currentPermutation`. For each lock strength `s`:
        i. Calculate the time required: `time = (s + factor - 1) / factor` (this is equivalent to `ceil(s / factor)` using integer arithmetic).
        ii. Add `time` to `totalTime`.
        iii. Update the factor for the next lock: `factor += k`.
    c. Update the global minimum time: `minTime = min(minTime, totalTime)`.
6. In the recursive step (for `i` from `index` to `n-1`):
    a. Swap the elements at `index` and `i` to create a new ordering to explore.
    b. Make a recursive call: `generatePermutations(index + 1, ...) `.
    c. Swap the elements back to their original positions to backtrack and explore other possibilities.
7. Initiate the process by calling `generatePermutations(0, initialListOfStrengths)`.
8. The final value of `minTime` is the answer.

## Dynamic Programming with Bitmasking
A more efficient approach uses dynamic programming with bitmasking. This technique is well-suited for problems with small constraints on `n` where we need to consider subsets of items. We can represent the set of broken locks using a bitmask. The state of our DP will be defined by this mask, and we'll compute the minimum time to break the corresponding set of locks by building up from smaller subsets to larger ones.
**Time:** O(n * 2^n) - We iterate through `2^n` masks. For each mask, we perform an inner loop that runs `n` times to check each bit. The operations inside the loop are constant time. · **Space:** O(2^n) - We use a DP array of size `2^n` to store the minimum time for each subset of locks.
**Pros:** Significantly more efficient than the brute-force permutation approach.; Guarantees finding the optimal solution by systematically exploring all valid state transitions.
**Cons:** The exponential time and space complexity limit its use to problems with small `n`.; Can be less intuitive to formulate compared to the direct brute-force approach.
### Explanation
We use a DP array, `dp`, of size `2^n`. `dp[mask]` stores the minimum time required to break the locks represented by the `mask`. A `1` at the `i`-th bit of the mask means the `i`-th lock (from the original input) has been broken. The state transition relies on identifying which lock was the last one broken to reach the current state `mask`. The number of set bits in a mask (`popcount(mask)`) tells us how many locks have been broken. If `c = popcount(mask)`, we are about to break the `c`-th lock in a sequence. The factor for this `c`-th break will always be `1 + (c-1) * k`, regardless of which specific `c` locks were broken or in what order. This allows us to build the solution iteratively.

```java
class Solution {
    public int minimumTime(int[] strength, int k) {
        int n = strength.length;
        int numMasks = 1 << n;
        long[] dp = new long[numMasks];
        java.util.Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 1; mask < numMasks; mask++) {
            int brokenLocksCount = Integer.bitCount(mask);
            long factor = 1 + (long)(brokenLocksCount - 1) * k;

            for (int j = 0; j < n; j++) {
                // Check if lock j is in the current set (mask)
                if ((mask & (1 << j)) != 0) {
                    int prevMask = mask ^ (1 << j);
                    if (dp[prevMask] != Long.MAX_VALUE) {
                        long timeForJ = (strength[j] + factor - 1) / factor;
                        dp[mask] = Math.min(dp[mask], dp[prevMask] + timeForJ);
                    }
                }
            }
        }
        return (int) dp[numMasks - 1];
    }
}
```
### Algorithm
1. Define a DP array, `dp`, of size `2^n`. `dp[mask]` will store the minimum time to break the set of locks represented by the `mask`.
2. Initialize all entries of `dp` to a large value (infinity), except for the base case.
3. Set the base case: `dp[0] = 0`, as it takes 0 time to break 0 locks.
4. Iterate through each `mask` from `1` to `(1<<n) - 1`.
5. For each `mask`, calculate the number of locks already broken, `c = Integer.bitCount(mask)`.
6. The factor for breaking the `c`-th lock in any sequence leading to this state is `factor = 1 + (long)(c - 1) * k`.
7. Iterate through each lock `j` from `0` to `n-1`.
8. Check if lock `j` is part of the current set (i.e., if the `j`-th bit is set in `mask`).
9. If it is, this lock `j` could have been the last one broken to reach the state `mask`. The previous state would be `prevMask = mask ^ (1 << j)`.
10. Calculate the time to break lock `j`: `timeForJ = (strength[j] + factor - 1) / factor`.
11. Update the `dp` value for the current mask: `dp[mask] = min(dp[mask], dp[prevMask] + timeForJ)`.
12. After iterating through all masks, the final answer is `dp[(1<<n) - 1]`, which is the minimum time to break all `n` locks.

# Solutions
### Java

```java
class Solution {
private
  List<Integer> strength;
private
  Integer[] f;
private
  int k;
private
  int n;
public
  int findMinimumTime(List<Integer> strength, int K) {
    n = strength.size();
    f = new Integer[1 << n];
    k = K;
    this.strength = strength;
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i == (1 << n) - 1) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int cnt = Integer.bitCount(i);
    int x = 1 + cnt * k;
    f[i] = 1 << 30;
    for (int j = 0; j < n; ++j) {
      if ((i >> j & 1) == 0) {
        f[i] = Math.min(f[i], dfs(i | 1 << j) + (strength.get(j) + x - 1) / x);
      }
    }
    return f[i];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMinimumTime(vector<int> &strength, int K) {
    int n = strength.size();
    int f[1 << n];
    memset(f, -1, sizeof(f));
    int k = K;
    auto dfs = [&](auto &&dfs, int i) -> int {
      if (i == (1 << n) - 1) {
        return 0;
      }
      if (f[i] != -1) {
        return f[i];
      }
      int cnt = __builtin_popcount(i);
      int x = 1 + k * cnt;
      f[i] = INT_MAX;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1 ^ 1) {
          f[i] = min(f[i], dfs(dfs, i | 1 << j) + (strength[j] + x - 1) / x);
        }
      }
      return f[i];
    };
    return dfs(dfs, 0);
  }
};

```

### Python

```python
class Solution:
    def findMinimumTime(self, strength: List[int], K: int) -> int: @ cache def dfs(i: int) -> int: if i == (1 << len(strength)) - 1: return 0 cnt = i . bit_count() x = 1 + cnt * K ans = inf for j, s in enumerate(strength): if i >> j & 1 ^ 1: ans = min(ans, dfs(i | 1 << j) + (s + x - 1) // x) return ans return dfs(0)

```