# Minimum Array Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-array-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-array-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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.

**Example 1:**

**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:**

**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] <= 105`
* `0 <= k <= 105`
* `0 <= op1, op2 <= nums.length`

# Approaches
## Brute-Force Backtracking
This approach uses a simple recursive method to explore all possible ways of applying the operations. For each number in the array, the function branches out, trying every valid choice: applying no operation, only Operation 1, only Operation 2, or both. This exhaustive search guarantees finding the optimal solution but at a very high computational cost, as it repeatedly solves the same subproblems.
**Time:** O(4^N) · **Space:** O(N)
**Pros:** Simple to understand and implement the logic.; Correctly explores the entire search space.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to build a recursive function that traverses the `nums` array. At each element, it makes a decision from a set of up to four choices. Each choice involves either using an operation (and its corresponding reduction) and decrementing the available operation count, or skipping the element. The function then proceeds to the next element. This process continues until all elements are considered. The maximum reduction found across all possible paths of decisions is the result. However, without memoization, the number of recursive calls grows exponentially with the size of the input, making it impractical.

```java
class Solution {
    private long[] nums_long;
    private int k_val, n;
    private long[] r1, r2, r_both;

    public long minArraySum(int[] nums, int k, int op1, int op2) {
        n = nums.length;
        this.k_val = k;
        this.nums_long = new long[n];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            this.nums_long[i] = nums[i];
            totalSum += nums[i];
        }

        precomputeReductions();

        long maxReduction = findMaxReduction(0, op1, op2);
        return totalSum - maxReduction;
    }

    private void precomputeReductions() {
        r1 = new long[n];
        r2 = new long[n];
        r_both = new long[n];

        for (int i = 0; i < n; i++) {
            long num = nums_long[i];
            // Reduction from Op1
            r1[i] = num - (long) Math.ceil(num / 2.0);

            // Reduction from Op2
            r2[i] = (num >= k_val) ? k_val : 0;

            // Reduction from both ops
            long finalVal1 = Long.MAX_VALUE;
            long valAfterOp1 = (long) Math.ceil(num / 2.0);
            if (valAfterOp1 >= k_val) {
                finalVal1 = valAfterOp1 - k_val;
            }

            long finalVal2 = Long.MAX_VALUE;
            if (num >= k_val) {
                long valAfterOp2 = num - k_val;
                finalVal2 = (long) Math.ceil(valAfterOp2 / 2.0);
            }

            long minFinalVal = Math.min(finalVal1, finalVal2);
            if (minFinalVal != Long.MAX_VALUE) {
                r_both[i] = num - minFinalVal;
            } else {
                r_both[i] = -1; // Mark as not possible
            }
        }
    }

    private long findMaxReduction(int index, int op1_left, int op2_left) {
        if (index == n) {
            return 0;
        }

        // Choice 1: No-op
        long maxRed = findMaxReduction(index + 1, op1_left, op2_left);

        // Choice 2: Op1 only
        if (op1_left > 0) {
            maxRed = Math.max(maxRed, r1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left));
        }

        // Choice 3: Op2 only
        if (op2_left > 0 && r2[index] > 0) {
            maxRed = Math.max(maxRed, r2[index] + findMaxReduction(index + 1, op1_left, op2_left - 1));
        }

        // Choice 4: Both ops
        if (op1_left > 0 && op2_left > 0 && r_both[index] != -1) {
            maxRed = Math.max(maxRed, r_both[index] + findMaxReduction(index + 1, op1_left - 1, op2_left - 1));
        }

        return maxRed;
    }
}
```
### Algorithm
1. Define a recursive function `findMaxReduction(index, op1_left, op2_left)` that calculates the maximum possible reduction for the subarray starting at `index` with `op1_left` and `op2_left` operations remaining.
2. **Base Case:** If `index` reaches the end of the array (`nums.length`), no more operations can be performed, so return 0.
3. **Recursive Step:** For the element `nums[index]`, explore four possibilities:
    a. **No Operation:** Make a recursive call for the next index with the same operation counts: `findMaxReduction(index + 1, op1_left, op2_left)`.
    b. **Operation 1:** If `op1_left > 0`, calculate the reduction from applying Operation 1 and add the result of the recursive call for the next index with decremented `op1_left`: `reduction1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left)`.
    c. **Operation 2:** If `op2_left > 0`, calculate the reduction from applying Operation 2 and add the result of the recursive call: `reduction2[index] + findMaxReduction(index + 1, op1_left, op2_left - 1)`.
    d. **Both Operations:** If `op1_left > 0` and `op2_left > 0`, calculate the combined reduction and add the result of the recursive call: `reduction_both[index] + findMaxReduction(index + 1, op1_left - 1, op2_left - 1)`.
4. The function returns the maximum value among the valid choices.
5. The initial call is `findMaxReduction(0, op1, op2)`. The final minimum sum is the total initial sum minus this maximum reduction.

## Dynamic Programming with Memoization
This problem can be optimally solved using dynamic programming. It's a classic example of a 0/1 Multiple-Choice Multidimensional Knapsack problem. We want to maximize the total reduction, which is the 'value', subject to the constraints on the number of available operations `op1` and `op2`, which are the 'weights' or 'capacities' of our knapsack. By systematically building up a solution for subproblems, we can find the global optimum efficiently.
**Time:** O(N * op1 * op2) · **Space:** O(N * op1 * op2)
**Pros:** Guarantees the optimal solution.; Efficient enough for the given constraints with polynomial time complexity.; Handles the complex dependencies between operation choices correctly.
**Cons:** The space complexity of O(N * op1 * op2) can be large, although it fits within the limits for this problem.; Can be slightly more complex to set up compared to a simple greedy approach (which would be incorrect here).
### Explanation
The most robust way to solve this is with dynamic programming. We can use a top-down approach with memoization, which is a natural extension of the brute-force backtracking solution. We define a function `solve(index, op1_left, op2_left)` and use a 3D array `memo[index][op1_left][op2_left]` to store the results of subproblems to avoid re-computation.

First, we pre-calculate the reduction we get for each number `nums[i]` for each type of operation (Op1 only, Op2 only, and both). The 'both' case requires checking the two possible orderings of operations to find the maximum reduction. Then, the recursive function explores the same four choices as the brute-force approach, but before computing, it checks if the result for the current state `(index, op1_left, op2_left)` is already in the memoization table. If so, it returns the stored value immediately. If not, it computes the result, stores it in the table, and then returns it.

This turns the exponential complexity of the naive recursion into a polynomial time solution, as each of the `N * op1 * op2` states is computed only once.

```java
class Solution {
    private long[] nums_long;
    private int k_val, n;
    private long[] r1, r2, r_both;
    private Long[][][] memo;

    public long minArraySum(int[] nums, int k, int op1, int op2) {
        n = nums.length;
        this.k_val = k;
        this.nums_long = new long[n];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            this.nums_long[i] = nums[i];
            totalSum += nums[i];
        }

        precomputeReductions();
        memo = new Long[n][op1 + 1][op2 + 1];

        long maxReduction = findMaxReduction(0, op1, op2);
        return totalSum - maxReduction;
    }

    private void precomputeReductions() {
        r1 = new long[n];
        r2 = new long[n];
        r_both = new long[n];

        for (int i = 0; i < n; i++) {
            long num = nums_long[i];
            r1[i] = num - (long) Math.ceil(num / 2.0);
            r2[i] = (num >= k_val) ? k_val : 0;

            long finalVal1 = Long.MAX_VALUE;
            long valAfterOp1 = (long) Math.ceil(num / 2.0);
            if (valAfterOp1 >= k_val) {
                finalVal1 = valAfterOp1 - k_val;
            }

            long finalVal2 = Long.MAX_VALUE;
            if (num >= k_val) {
                long valAfterOp2 = num - k_val;
                finalVal2 = (long) Math.ceil(valAfterOp2 / 2.0);
            }

            long minFinalVal = Math.min(finalVal1, finalVal2);
            if (minFinalVal != Long.MAX_VALUE) {
                r_both[i] = num - minFinalVal;
            } else {
                r_both[i] = -1; // Mark as not possible
            }
        }
    }

    private long findMaxReduction(int index, int op1_left, int op2_left) {
        if (index == n) {
            return 0;
        }
        if (memo[index][op1_left][op2_left] != null) {
            return memo[index][op1_left][op2_left];
        }

        // Choice 1: No-op
        long maxRed = findMaxReduction(index + 1, op1_left, op2_left);

        // Choice 2: Op1 only
        if (op1_left > 0) {
            maxRed = Math.max(maxRed, r1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left));
        }

        // Choice 3: Op2 only
        if (op2_left > 0 && r2[index] > 0) {
            maxRed = Math.max(maxRed, r2[index] + findMaxReduction(index + 1, op1_left, op2_left - 1));
        }

        // Choice 4: Both ops
        if (op1_left > 0 && op2_left > 0 && r_both[index] != -1) {
            maxRed = Math.max(maxRed, r_both[index] + findMaxReduction(index + 1, op1_left - 1, op2_left - 1));
        }

        return memo[index][op1_left][op2_left] = maxRed;
    }
}
```
*Note: A bottom-up iterative DP approach is also possible and can save recursion overhead. The space complexity can also be optimized to O(op1 * op2) by only keeping track of the DP states for the previous and current items.*
### Algorithm
1.  **Model as Knapsack:** Frame the problem as a 0/1 Multiple-Choice Multidimensional Knapsack Problem. Each number `nums[i]` is an 'item'. For each item, there are four mutually exclusive 'choices' (no-op, op1, op2, both), each with a 'value' (the reduction) and a 'weight' (the cost in `op1` and `op2`).
2.  **Pre-computation:** For each number `nums[i]`, calculate the potential reduction for each of the three operations: `reduction1`, `reduction2`, and `reduction_both`.
3.  **DP State:** Define a 3D DP table `dp[i][j][k]`, where `dp[i][j][k]` stores the maximum reduction achievable by considering the first `i` numbers from the `nums` array, using exactly `j` of Operation 1 and `k` of Operation 2.
4.  **Initialization:** Initialize the `dp` table with a value indicating it's not yet computed (e.g., -1), with base cases `dp[0][j][k] = 0` (or handle within recursion).
5.  **Transition (Top-Down/Memoization):** The recursive function `solve(i, j, k)` computes `dp[i][j][k]` by taking the maximum of the four choices for item `i`, using the results from `solve(i-1, ...)` for the subproblems.
6.  **Transition (Bottom-Up):** Iterate from `i = 1 to n`, `j = 0 to op1`, `k = 0 to op2`. For each `dp[i][j][k]`, calculate its value based on the four choices for item `i-1` and the previously computed states in `dp[i-1]`: 
    `dp[i][j][k] = max(`
    `  dp[i-1][j][k],`
    `  dp[i-1][j-1][k] + reduction1[i-1],`
    `  dp[i-1][j][k-1] + reduction2[i-1],`
    `  dp[i-1][j-1][k-1] + reduction_both[i-1]`
    ` )`
    (ensuring `j` and `k` are sufficient for each choice).
7.  **Result:** The maximum total reduction is `dp[n][op1][op2]`. The final answer is the initial total sum minus this reduction.

# Solutions
### Java

```java
class Solution {
public
  int minArraySum(int[] nums, int d, int op1, int op2) {
    int n = nums.length;
    int[][][] f = new int[n + 1][op1 + 1][op2 + 1];
    final int inf = 1 << 29;
    for (var g : f) {
      for (var h : g) {
        Arrays.fill(h, inf);
      }
    }
    f[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      int x = nums[i - 1];
      for (int j = 0; j <= op1; ++j) {
        for (int k = 0; k <= op2; ++k) {
          f[i][j][k] = f[i - 1][j][k] + x;
          if (j > 0) {
            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);
          }
          if (k > 0 && x >= d) {
            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
          }
          if (j > 0 && k > 0) {
            int y = (x + 1) / 2;
            if (y >= d) {
              f[i][j][k] =
                  Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));
            }
            if (x >= d) {
              f[i][j][k] = Math.min(f[i][j][k],
                                    f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);
            }
          }
        }
      }
    }
    int ans = inf;
    for (int j = 0; j <= op1; ++j) {
      for (int k = 0; k <= op2; ++k) {
        ans = Math.min(ans, f[n][j][k]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minArraySum(vector<int> &nums, int d, int op1, int op2) {
    int n = nums.size();
    int f[n + 1][op1 + 1][op2 + 1];
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      int x = nums[i - 1];
      for (int j = 0; j <= op1; ++j) {
        for (int k = 0; k <= op2; ++k) {
          f[i][j][k] = f[i - 1][j][k] + x;
          if (j > 0) {
            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);
          }
          if (k > 0 && x >= d) {
            f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
          }
          if (j > 0 && k > 0) {
            int y = (x + 1) / 2;
            if (y >= d) {
              f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));
            }
            if (x >= d) {
              f[i][j][k] =
                  min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);
            }
          }
        }
      }
    }
    int ans = INT_MAX;
    for (int j = 0; j <= op1; ++j) {
      for (int k = 0; k <= op2; ++k) {
        ans = min(ans, f[n][j][k]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minArraySum(self, nums: List[int], d: int, op1: int, op2: int) -> int: n = len(nums) f = [[[inf] * (op2 + 1) for _ in range(op1 + 1)] for _ in range(n + 1)] f[0][0][0] = 0 for i, x in enumerate(nums, 1): for j in range(op1 + 1): for k in range(op2 + 1): f[i][j][k] = f[i - 1][j][k] + x if j > 0: f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) // 2) if k > 0 and x >= d: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d)) if j > 0 and k > 0: y = (x + 1) // 2 if y >= d: f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + y - d) if x >= d: f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) // 2) ans = inf for j in range(op1 + 1): for k in range(op2 + 1): ans = min(ans, f[n][j][k]) return ans

```