Minimum Operations to Exceed Threshold Value II
You are given a 0-indexed integer array nums, and an integer k.
You are allowed to perform some operations on nums, where in a single operation, you can:
- Select the two smallest integers
xandyfromnums. - Remove
xandyfromnums. - Insert
(min(x, y) * 2 + max(x, y))at any position in the array.
Note that you can only apply the described operation if nums contains at least two elements.
Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.
Example 1
Input
nums = [2,11,10,1,3], k = 10Output
2After combining the two smallest values twice,
nums becomes [10, 11, 10], so all elements are at least 10, and this is the minimum number of operations.Example 2
Input
nums = [1,1,2,4,9], k = 20Output
4After four operations,
nums becomes [33], so all elements are at least 20, and this is the minimum number of operations.Constraints
- 2 <= nums.length <= 2 * 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
- The input is generated such that an answer always exists. That is, after performing some number of operations, all elements of the array are greater than or equal to
k.