3376. Minimum Time to Break Locks I Medium
1/**
2 * [3376] Minimum Time to Break Locks I
3 *
4 * 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.
5 * To break a lock, Bob uses a sword with the following characteristics:
6 *
7 * The initial energy of the sword is 0.
8 * The initial factor <font face="monospace">x</font> by which the energy of the sword increases is 1.
9 * Every minute, the energy of the sword increases by the current factor x.
10 * To break the i^th lock, the energy of the sword must reach at least strength[i].
11 * After breaking a lock, the energy of the sword resets to 0, and the factor x increases by a given value k.
12 *
13 * Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.
14 * Return the minimum time required for Bob to break all n locks.
15 *
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">strength = [3,4,1], k = 1</span>
19 * Output: <span class="example-io">4</span>
20 * Explanation:
21 * <table style="border: 1px solid black;">
22 * <tbody>
23 * <tr>
24 * <th style="border: 1px solid black;">Time</th>
25 * <th style="border: 1px solid black;">Energy</th>
26 * <th style="border: 1px solid black;">x</th>
27 * <th style="border: 1px solid black;">Action</th>
28 * <th style="border: 1px solid black;">Updated x</th>
29 * </tr>
30 * <tr>
31 * <td style="border: 1px solid black;">0</td>
32 * <td style="border: 1px solid black;">0</td>
33 * <td style="border: 1px solid black;">1</td>
34 * <td style="border: 1px solid black;">Nothing</td>
35 * <td style="border: 1px solid black;">1</td>
36 * </tr>
37 * <tr>
38 * <td style="border: 1px solid black;">1</td>
39 * <td style="border: 1px solid black;">1</td>
40 * <td style="border: 1px solid black;">1</td>
41 * <td style="border: 1px solid black;">Break 3^rd Lock</td>
42 * <td style="border: 1px solid black;">2</td>
43 * </tr>
44 * <tr>
45 * <td style="border: 1px solid black;">2</td>
46 * <td style="border: 1px solid black;">2</td>
47 * <td style="border: 1px solid black;">2</td>
48 * <td style="border: 1px solid black;">Nothing</td>
49 * <td style="border: 1px solid black;">2</td>
50 * </tr>
51 * <tr>
52 * <td style="border: 1px solid black;">3</td>
53 * <td style="border: 1px solid black;">4</td>
54 * <td style="border: 1px solid black;">2</td>
55 * <td style="border: 1px solid black;">Break 2^nd Lock</td>
56 * <td style="border: 1px solid black;">3</td>
57 * </tr>
58 * <tr>
59 * <td style="border: 1px solid black;">4</td>
60 * <td style="border: 1px solid black;">3</td>
61 * <td style="border: 1px solid black;">3</td>
62 * <td style="border: 1px solid black;">Break 1^st Lock</td>
63 * <td style="border: 1px solid black;">3</td>
64 * </tr>
65 * </tbody>
66 * </table>
67 * The locks cannot be broken in less than 4 minutes; thus, the answer is 4.
68 * </div>
69 * <strong class="example">Example 2:
70 * <div class="example-block">
71 * Input: <span class="example-io">strength = [2,5,4], k = 2</span>
72 * Output: <span class="example-io">5</span>
73 * Explanation:
74 * <table style="border: 1px solid black;">
75 * <tbody>
76 * <tr>
77 * <th style="border: 1px solid black;">Time</th>
78 * <th style="border: 1px solid black;">Energy</th>
79 * <th style="border: 1px solid black;">x</th>
80 * <th style="border: 1px solid black;">Action</th>
81 * <th style="border: 1px solid black;">Updated x</th>
82 * </tr>
83 * <tr>
84 * <td style="border: 1px solid black;">0</td>
85 * <td style="border: 1px solid black;">0</td>
86 * <td style="border: 1px solid black;">1</td>
87 * <td style="border: 1px solid black;">Nothing</td>
88 * <td style="border: 1px solid black;">1</td>
89 * </tr>
90 * <tr>
91 * <td style="border: 1px solid black;">1</td>
92 * <td style="border: 1px solid black;">1</td>
93 * <td style="border: 1px solid black;">1</td>
94 * <td style="border: 1px solid black;">Nothing</td>
95 * <td style="border: 1px solid black;">1</td>
96 * </tr>
97 * <tr>
98 * <td style="border: 1px solid black;">2</td>
99 * <td style="border: 1px solid black;">2</td>
100 * <td style="border: 1px solid black;">1</td>
101 * <td style="border: 1px solid black;">Break 1^st Lock</td>
102 * <td style="border: 1px solid black;">3</td>
103 * </tr>
104 * <tr>
105 * <td style="border: 1px solid black;">3</td>
106 * <td style="border: 1px solid black;">3</td>
107 * <td style="border: 1px solid black;">3</td>
108 * <td style="border: 1px solid black;">Nothing</td>
109 * <td style="border: 1px solid black;">3</td>
110 * </tr>
111 * <tr>
112 * <td style="border: 1px solid black;">4</td>
113 * <td style="border: 1px solid black;">6</td>
114 * <td style="border: 1px solid black;">3</td>
115 * <td style="border: 1px solid black;">Break 2^n^d Lock</td>
116 * <td style="border: 1px solid black;">5</td>
117 * </tr>
118 * <tr>
119 * <td style="border: 1px solid black;">5</td>
120 * <td style="border: 1px solid black;">5</td>
121 * <td style="border: 1px solid black;">5</td>
122 * <td style="border: 1px solid black;">Break 3^r^d Lock</td>
123 * <td style="border: 1px solid black;">7</td>
124 * </tr>
125 * </tbody>
126 * </table>
127 * The locks cannot be broken in less than 5 minutes; thus, the answer is 5.
128 * </div>
129 *
130 * Constraints:
131 *
132 * n == strength.length
133 * 1 <= n <= 8
134 * 1 <= K <= 10
135 * 1 <= strength[i] <= 10^6
136 *
137 */
138pub struct Solution {}
139
140// problem: https://leetcode.com/problems/minimum-time-to-break-locks-i/
141// discuss: https://leetcode.com/problems/minimum-time-to-break-locks-i/discuss/?currentPage=1&orderBy=most_votes&query=
142
143// submission codes start here
144
145impl Solution {
146 pub fn find_minimum_time(strength: Vec<i32>, k: i32) -> i32 {
147 0
148 }
149}
150
151// submission codes end
152
153#[cfg(test)]
154mod tests {
155 use super::*;
156
157 #[test]
158 fn test_3376() {
159 }
160}
161Back
© 2025 bowen.ge All Rights Reserved.