# 13.02.2025 [3066. Minimum Operations to Exceed Threshold Value II]
Count nums += min(x,y)*2+max(x,y) < k #medium #heap
13.02.2025
3066. Minimum Operations to Exceed Threshold Value II medium blog post substack youtube
Join me on Telegram
Problem TLDR
Count nums += min(x,y)*2+max(x,y) < k #medium #heap
Intuition
There is only a heap solution.
Approach
some small tricks are possible, given that the result is guaranteed by rules
in-place heap is possible
Complexity
Time complexity: $$O(nlog(n))$$
Space complexity: $$O(n)$$
Code
fun minOperations(nums: IntArray, k: Int): Int {
val q = PriorityQueue(nums.map { 1L * it })
while (q.peek() < k) q += q.poll() * 2 + q.poll()
return nums.size - q.size
}
pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
let mut q = BinaryHeap::from_iter(nums.iter().map(|x| -x as i64));
while let Some(x) = q.pop().filter(|&x| x > -k as i64) {
let y = q.pop().unwrap(); q.push(x * 2 + y)
}; (nums.len() - q.len() - 1) as i32
}
int minOperations(vector<int>& n, int k) {
priority_queue<long, vector<long>, greater<>> q(begin(n), end(n));
while (q.top() < k) {
auto x = 2 * q.top(); q.pop(); x += q.top(); q.pop();
q.push(x);
}
return size(n) - size(q);
}