Minimum Array Sum

Med

#2991Time: O(4^N)Space: O(N)

Patterns

Dynamic Programming

Data structures

Array

Prompt

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] <= 10⁵
0 <= k <= 10⁵
0 <= op1, op2 <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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.
Base Case: If index reaches the end of the array (nums.length), no more operations can be performed, so return 0.
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).
The function returns the maximum value among the valid choices.
The initial call is findMaxReduction(0, op1, op2). The final minimum sum is the total initial sum minus this maximum reduction.

Walkthrough

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.

1class Solution {2    private long[] nums_long;3    private int k_val, n;4    private long[] r1, r2, r_both;5 6    public long minArraySum(int[] nums, int k, int op1, int op2) {7        n = nums.length;8        this.k_val = k;9        this.nums_long = new long[n];10        long totalSum = 0;11        for (int i = 0; i < n; i++) {12            this.nums_long[i] = nums[i];13            totalSum += nums[i];14        }15 16        precomputeReductions();17 18        long maxReduction = findMaxReduction(0, op1, op2);19        return totalSum - maxReduction;20    }21 22    private void precomputeReductions() {23        r1 = new long[n];24        r2 = new long[n];25        r_both = new long[n];26 27        for (int i = 0; i < n; i++) {28            long num = nums_long[i];29            // Reduction from Op130            r1[i] = num - (long) Math.ceil(num / 2.0);31 32            // Reduction from Op233            r2[i] = (num >= k_val) ? k_val : 0;34 35            // Reduction from both ops36            long finalVal1 = Long.MAX_VALUE;37            long valAfterOp1 = (long) Math.ceil(num / 2.0);38            if (valAfterOp1 >= k_val) {39                finalVal1 = valAfterOp1 - k_val;40            }41 42            long finalVal2 = Long.MAX_VALUE;43            if (num >= k_val) {44                long valAfterOp2 = num - k_val;45                finalVal2 = (long) Math.ceil(valAfterOp2 / 2.0);46            }47 48            long minFinalVal = Math.min(finalVal1, finalVal2);49            if (minFinalVal != Long.MAX_VALUE) {50                r_both[i] = num - minFinalVal;51            } else {52                r_both[i] = -1; // Mark as not possible53            }54        }55    }56 57    private long findMaxReduction(int index, int op1_left, int op2_left) {58        if (index == n) {59            return 0;60        }61 62        // Choice 1: No-op63        long maxRed = findMaxReduction(index + 1, op1_left, op2_left);64 65        // Choice 2: Op1 only66        if (op1_left > 0) {67            maxRed = Math.max(maxRed, r1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left));68        }69 70        // Choice 3: Op2 only71        if (op2_left > 0 && r2[index] > 0) {72            maxRed = Math.max(maxRed, r2[index] + findMaxReduction(index + 1, op1_left, op2_left - 1));73        }74 75        // Choice 4: Both ops76        if (op1_left > 0 && op2_left > 0 && r_both[index] != -1) {77            maxRed = Math.max(maxRed, r_both[index] + findMaxReduction(index + 1, op1_left - 1, op2_left - 1));78        }79 80        return maxRed;81    }82}

Complexity

Time

O(4^N)

Space

O(N)

Trade-offs

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.

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.

Algorithm

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).
Pre-computation: For each number nums[i], calculate the potential reduction for each of the three operations: reduction1, reduction2, and reduction_both.
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.
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).
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.
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).
Result: The maximum total reduction is dp[n][op1][op2]. The final answer is the initial total sum minus this reduction.

Walkthrough

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.

1class Solution {2    private long[] nums_long;3    private int k_val, n;4    private long[] r1, r2, r_both;5    private Long[][][] memo;6 7    public long minArraySum(int[] nums, int k, int op1, int op2) {8        n = nums.length;9        this.k_val = k;10        this.nums_long = new long[n];11        long totalSum = 0;12        for (int i = 0; i < n; i++) {13            this.nums_long[i] = nums[i];14            totalSum += nums[i];15        }16 17        precomputeReductions();18        memo = new Long[n][op1 + 1][op2 + 1];19 20        long maxReduction = findMaxReduction(0, op1, op2);21        return totalSum - maxReduction;22    }23 24    private void precomputeReductions() {25        r1 = new long[n];26        r2 = new long[n];27        r_both = new long[n];28 29        for (int i = 0; i < n; i++) {30            long num = nums_long[i];31            r1[i] = num - (long) Math.ceil(num / 2.0);32            r2[i] = (num >= k_val) ? k_val : 0;33 34            long finalVal1 = Long.MAX_VALUE;35            long valAfterOp1 = (long) Math.ceil(num / 2.0);36            if (valAfterOp1 >= k_val) {37                finalVal1 = valAfterOp1 - k_val;38            }39 40            long finalVal2 = Long.MAX_VALUE;41            if (num >= k_val) {42                long valAfterOp2 = num - k_val;43                finalVal2 = (long) Math.ceil(valAfterOp2 / 2.0);44            }45 46            long minFinalVal = Math.min(finalVal1, finalVal2);47            if (minFinalVal != Long.MAX_VALUE) {48                r_both[i] = num - minFinalVal;49            } else {50                r_both[i] = -1; // Mark as not possible51            }52        }53    }54 55    private long findMaxReduction(int index, int op1_left, int op2_left) {56        if (index == n) {57            return 0;58        }59        if (memo[index][op1_left][op2_left] != null) {60            return memo[index][op1_left][op2_left];61        }62 63        // Choice 1: No-op64        long maxRed = findMaxReduction(index + 1, op1_left, op2_left);65 66        // Choice 2: Op1 only67        if (op1_left > 0) {68            maxRed = Math.max(maxRed, r1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left));69        }70 71        // Choice 3: Op2 only72        if (op2_left > 0 && r2[index] > 0) {73            maxRed = Math.max(maxRed, r2[index] + findMaxReduction(index + 1, op1_left, op2_left - 1));74        }75 76        // Choice 4: Both ops77        if (op1_left > 0 && op2_left > 0 && r_both[index] != -1) {78            maxRed = Math.max(maxRed, r_both[index] + findMaxReduction(index + 1, op1_left - 1, op2_left - 1));79        }80 81        return memo[index][op1_left][op2_left] = maxRed;82    }83}

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.

Complexity

Time

O(N * op1 * op2)

Space

O(N * op1 * op2)

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int minArraySum(int[] nums, int d, int op1, int op2) {4    int n = nums.length;5    int[][][] f = new int[n + 1][op1 + 1][op2 + 1];6    final int inf = 1 << 29;7    for (var g : f) {8      for (var h : g) {9        Arrays.fill(h, inf);10      }11    }12    f[0][0][0] = 0;13    for (int i = 1; i <= n; ++i) {14      int x = nums[i - 1];15      for (int j = 0; j <= op1; ++j) {16        for (int k = 0; k <= op2; ++k) {17          f[i][j][k] = f[i - 1][j][k] + x;18          if (j > 0) {19            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);20          }21          if (k > 0 && x >= d) {22            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));23          }24          if (j > 0 && k > 0) {25            int y = (x + 1) / 2;26            if (y >= d) {27              f[i][j][k] =28                  Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));29            }30            if (x >= d) {31              f[i][j][k] = Math.min(f[i][j][k],32                                    f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);33            }34          }35        }36      }37    }38    int ans = inf;39    for (int j = 0; j <= op1; ++j) {40      for (int k = 0; k <= op2; ++k) {41        ans = Math.min(ans, f[n][j][k]);42      }43    }44    return ans;45  }46}

1class Solution {2public:3  int minArraySum(vector<int> &nums, int d, int op1, int op2) {4    int n = nums.size();5    int f[n + 1][op1 + 1][op2 + 1];6    memset(f, 0x3f, sizeof f);7    f[0][0][0] = 0;8    for (int i = 1; i <= n; ++i) {9      int x = nums[i - 1];10      for (int j = 0; j <= op1; ++j) {11        for (int k = 0; k <= op2; ++k) {12          f[i][j][k] = f[i - 1][j][k] + x;13          if (j > 0) {14            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2);15          }16          if (k > 0 && x >= d) {17            f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));18          }19          if (j > 0 && k > 0) {20            int y = (x + 1) / 2;21            if (y >= d) {22              f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d));23            }24            if (x >= d) {25              f[i][j][k] =26                  min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) / 2);27            }28          }29        }30      }31    }32    int ans = INT_MAX;33    for (int j = 0; j <= op1; ++j) {34      for (int k = 0; k <= op2; ++k) {35        ans = min(ans, f[n][j][k]);36      }37    }38    return ans;39  }40};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem