Minimum Array Sum

You're given an integer array nums and three integers k, op1, and op2. You can apply two kinds of operations:

• Halve: pick an index i and replace nums[i] with nums[i] / 2, rounded up. You can do this at most op1 times in total, and at most once per index.
• Subtract: pick an index i where nums[i] ≥ k and replace nums[i] with nums[i] - k. You can do this at most op2 times in total, and at most once per index.

The same index may receive both operations (each at most once), in either order. The "nums[i] ≥ k" check for Subtract uses the value at the moment you subtract, so the order can matter.

Return the smallest possible sum of nums after applying any number of operations within these limits. You don't have to use all of them.

Each element ends up in one of four states: untouched, halved, reduced by k, or both. Its final value only depends on its own state, and the only thing linking elements together is the two shared budgets. That is a knapsack: items (elements), each with a few options, each option costing some of budget 1 and some of budget 2.

So define dp[a][b] as the smallest sum of the elements processed so far using at most a halvings and b subtractions. For each new element, try all four options and take the best.

The "both" option needs one extra thought. Halving then subtracting gives ceil(x / 2) - k, which is smaller, but it is only legal if ceil(x / 2) ≥ k. Subtracting then halving gives ceil((x - k) / 2) and only needs x ≥ k. Take the best legal one.

Greedy choices (halve the largest values, subtract from the rest) are tempting, but the interaction between the two operations and the ≥ k rule makes them fail on some inputs. The DP avoids having to prove a greedy rule.

def min_array_sum(nums: list[int], k: int, op1: int, op2: int) -> int:
    dp = [[0] * (op2 + 1) for _ in range(op1 + 1)]
    for x in nums:
        half = (x + 1) // 2
        both = None
        if x >= k:
            both = (x - k + 1) // 2
        if half >= k:
            both = half - k if both is None else min(both, half - k)
        for a in range(op1, -1, -1):
            row, prev = dp[a], dp[a - 1] if a else None
            for b in range(op2, -1, -1):
                best = row[b] + x
                if prev is not None:
                    best = min(best, prev[b] + half)
                if b and x >= k:
                    best = min(best, row[b - 1] + x - k)
                if prev is not None and b and both is not None:
                    best = min(best, prev[b - 1] + both)
                row[b] = best
    return dp[op1][op2]

function minArraySum(nums, k, op1, op2) {
  const dp = Array.from({ length: op1 + 1 }, () => new Array(op2 + 1).fill(0));
  for (const x of nums) {
    const half = Math.ceil(x / 2);
    let both = Infinity;
    if (x >= k) both = Math.ceil((x - k) / 2);
    if (half >= k) both = Math.min(both, half - k);
    for (let a = op1; a >= 0; a--) {
      for (let b = op2; b >= 0; b--) {
        let best = dp[a][b] + x;
        if (a > 0) best = Math.min(best, dp[a - 1][b] + half);
        if (b > 0 && x >= k) best = Math.min(best, dp[a][b - 1] + x - k);
        if (a > 0 && b > 0) best = Math.min(best, dp[a - 1][b - 1] + both);
        dp[a][b] = best;
      }
    }
  }
  return dp[op1][op2];
}

Start by saying why greedy is risky here: two operations interact and the ≥ k condition depends on order. Then frame it as a knapsack with two capacities. Interviewers want to hear the state definition stated precisely ("best sum of the first i elements using at most a and b operations") before you code.

Spend a minute on the "both" option and the order question, and use a tiny example like x = 7, k = 5 to show you checked it. Finish by mentioning the downward iteration and the resulting O(op1 · op2) memory.