Minimum Time to Break Locks I
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
xby which the energy of the sword increases is1. - Every minute, the energy of the sword increases by the current factor
x. - To break the
i^thlock, the energy of the sword must reach at leaststrength[i]. - After breaking a lock, the energy of the sword resets to
0, and the factorxincreases by a given valuek.
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 = 1Output
4The locks cannot be broken in less than 4 minutes; thus, the answer is 4.
Example 2
Input
strength = [2,5,4], k = 2Output
5The 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] <= 10^6