Minimum Sum After K Ceiling Halvings
Problem statement
You are given an array of positive integers nums and an integer k. One operation is:
- pick any element
xof the array, - replace it with
x / 2rounded up (so 7 becomes 4, and 1 stays 1).
You must do exactly k operations, and you may pick the same element more than once. Return the smallest possible sum of the array after the k operations.
Function
minSumAfterHalvings(nums: int[], k: int) → intExamples
Example 1
nums = [10,3,7]k = 2return = 12Halve 10 to 5 (sum 15), then halve 7 to 4 (sum 12). No other pair of moves does better: for example halving 10 twice gives 3 + 3 + 7 = 13.
Example 2
nums = [1,1]k = 5return = 2Halving 1 with rounding up gives 1 again, so all five moves change nothing. The sum stays 2.
Example 3
nums = [9]k = 3return = 29 becomes 5, then 3, then 2.
Constraints
1 <= nums.length <= 10^41 <= nums[i] <= 10^41 <= k <= 10^5