3066: Minimum-Operations-to-Exceed-Threshold-Value-II
Medium
table of contents
Where did all my beloved string manipulation questions go?! Slight disaster, but it is a-ok, since today’s question is a priority_queue question.
Starting off, we know we can ignore all the values
greater than k as they already satisfy the
pre-requisite. This means we can start off by pre-computing all
the values that are smaller than k as they
are the only relevant values needed to solve this
question.
Consequently, once we do pre-compute all the relevant
values, the only way to possibly count the minimum
number of the previously described operation is if we just…
repeat the operation… over and over again… yeah, not the
fanciest solution ever. However, the most efficient
data-structure for this question is a priority_queue (or a
min heap) as at every step, we have to retrieve the
2 smallest values and re-insert the new
calculated value back into the list while
maintaining the same order (a task perfect for a
priority_queue).
Therefore, you just repeat the operation, until the
priority_queue is empty or has size equal to 1
(whilst keeping a counter ans of all the operations that
have been initialized)
code
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> valid;
for (int &n : nums) {
if (n < k) {
valid.push(n);
}
}
if (valid.size() == 0) return 0;
int ans = 0;
while (valid.size() > 1) {
++ans;
int min1 = valid.top();
valid.pop();
int min2 = valid.top();
valid.pop();
int new_value = min1 + min2;
if (new_value >= k) continue;
new_value += min1;
if (new_value >= k) continue;
else {
valid.push(new_value);
}
}
return valid.size() == 1 ? ans + 1 : ans;
}
};