Combine the Two Smallest Until All Reach k
Problem statement
You have a list of positive integers nums and a threshold k. One combine step removes the two smallest values x <= y from the list and adds the single value 2 * x + y.
Keep combining while the smallest value in the list is below k. Return how many steps you made. If the smallest value is still below k when only one value is left, return -1.
Note that new values can be larger than a 32-bit integer can hold.
Function
minCombineOps(nums: int[], k: int) → intExamples
Example 1
nums = [7,1,12,3]k = 9return = 2Combine 1 and 3 into 1 x 2 + 3 = 5: [7, 12, 5]. Combine 5 and 7 into 5 x 2 + 7 = 17: [12, 17]. Every value is now at least 9, after 2 operations.
Example 2
nums = [5,6]k = 5return = 0Both values are already at least 5, so no operation is needed: 0.
Example 3
nums = [1,2,1]k = 20return = -1Combine 1 and 1 into 3: [2, 3]. Combine 2 and 3 into 7: [7]. Only one value is left and it is below 20, so it is impossible: -1.
Constraints
1 <= nums.length <= 50001 <= nums[i] <= 10^91 <= k <= 10^9