Problem

You are given an integer array nums and three integers k, op1, and op2.

You can perform the following operations on nums:

  • Operation 1 : Choose an index i and divide nums[i] by 2, rounding up to the nearest whole number. You can perform this operation at most op1 times, and not more than once per index.
  • Operation 2 : Choose an index i and subtract k from nums[i], but only if nums[i] is greater than or equal to k. You can perform this operation at most op2 times, and not more than once per index.

Note: Both operations can be applied to the same index, but at most once each.

Return the minimum possible sum of all elements in nums after performing any number of operations.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1

Output: 23

Explanation:

  * Apply Operation 2 to `nums[1] = 8`, making `nums[1] = 5`.
  * Apply Operation 1 to `nums[3] = 19`, making `nums[3] = 10`.
  * The resulting array becomes `[2, 5, 3, 10, 3]`, which has the minimum possible sum of 23 after applying the operations.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: nums = [2,4,3], k = 3, op1 = 2, op2 = 1

Output: 3

Explanation:

  * Apply Operation 1 to `nums[0] = 2`, making `nums[0] = 1`.
  * Apply Operation 1 to `nums[1] = 4`, making `nums[1] = 2`.
  * Apply Operation 2 to `nums[2] = 3`, making `nums[2] = 0`.
  * The resulting array becomes `[1, 2, 0]`, which has the minimum possible sum of 3 after applying the operations.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 10^5
  • 0 <= k <= 10^5
  • 0 <= op1, op2 <= nums.length

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

Each operation can be applied at most once per index, and both can be applied to the same index. We want to minimize the sum by choosing which operation(s) to apply to each index, given the limits. This is a classic DP problem with state compression: for each index, track the number of op1 and op2 used, and the minimum sum achievable.

Approach

  1. Use DP with states (i, op1_used, op2_used) representing the minimum sum for the first i elements, using op1_used and op2_used operations.
  2. For each index, try:
    • No operation.
    • Only op1 (divide by 2, round up).
    • Only op2 (subtract k if possible).
    • Both operations (divide by 2, then subtract k if possible).
  3. Update DP accordingly, ensuring not to exceed op1/op2 limits and not to apply more than once per index.
  4. The answer is the minimum sum over all valid states after processing all elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def minimum_array_sum(nums: list[int], k: int, op1: int, op2: int) -> int:
    import math
    n = len(nums)
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(i: int, o1: int, o2: int) -> int:
        if i == n:
            return 0
        res = nums[i] + dp(i+1, o1, o2)
        if o1 < op1:
            res = min(res, math.ceil(nums[i]/2) + dp(i+1, o1+1, o2))
        if o2 < op2 and nums[i] >= k:
            res = min(res, nums[i]-k + dp(i+1, o1, o2+1))
        if o1 < op1 and o2 < op2 and math.ceil(nums[i]/2) >= k:
            res = min(res, math.ceil(nums[i]/2)-k + dp(i+1, o1+1, o2+1))
        return res
    return dp(0, 0, 0)

Complexity

  • ⏰ Time complexity: O(n * op1 * op2)
    • DP over n elements and op1/op2 states.
  • 🧺 Space complexity: O(n * op1 * op2)
    • For DP cache.