Minimum Array Sum
MedPrompt
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
iand dividenums[i]by 2, rounding up to the nearest whole number. You can perform this operation at mostop1times, and not more than once per index. - Operation 2: Choose an index
iand subtractkfromnums[i], but only ifnums[i]is greater than or equal tok. You can perform this operation at mostop2times, 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, makingnums[1] = 5. - Apply Operation 1 to
nums[3] = 19, makingnums[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, makingnums[0] = 1. - Apply Operation 1 to
nums[1] = 4, makingnums[1] = 2. - Apply Operation 2 to
nums[2] = 3, makingnums[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 <= 1000 <= nums[i] <= 1050 <= k <= 1050 <= 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 atindexwithop1_leftandop2_leftoperations remaining. - Base Case: If
indexreaches 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: Ifop1_left > 0, calculate the reduction from applying Operation 1 and add the result of the recursive call for the next index with decrementedop1_left:reduction1[index] + findMaxReduction(index + 1, op1_left - 1, op2_left). c. Operation 2: Ifop2_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: Ifop1_left > 0andop2_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.
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; }}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.
Solutions
Solution
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; }}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.