FastPrepMinimum Sum After K Ceiling Halvings
Problems/Minimum Sum After K Ceiling Halvings

Minimum Sum After K Ceiling Halvings

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: With K moves, where one move replaces any array element by half of it rounded up, make the final total as small as possible. This was the first of two coding items in the candidate's first DSA round, and a priority queue was the reported solution.

The report gives no limits or examples and does not say whether values can be zero or negative. Here the values are positive (1 to 10^4), there are up to 10^4 of them, K is 1 to 10^5, and the same element may be picked again. The examples are our own.

The judged task matches the report at about 95%.

You are given an array of positive integers nums and an integer k. One operation is:

  1. pick any element x of the array,
  2. replace it with x / 2 rounded 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) → int

Examples

Example 1

nums = [10,3,7]k = 2return = 12

Halve 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 = 2

Halving 1 with rounding up gives 1 again, so all five moves change nothing. The sum stays 2.

Example 3

nums = [9]k = 3return = 2

9 becomes 5, then 3, then 2.

Constraints

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 10^5

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public int minSumAfterHalvings(int[] nums, int k) {
    // Write your code here.
}
Checking account…