Minimum Array Sum — Solution in Python, Java & C++
Minimum Array Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Minimum Array Sum is a medium coding problem on arrays and dynamic programming, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and three integers k, op1 and op2. Two operations are available:
- Operation 1: pick an index
iand replacenums[i]withnums[i] / 2rounded up. You may do this at mostop1times in total, and at most once per index. - Operation 2: pick an index
iwithnums[i] >= kand subtractkfrom it. You may do this at mostop2times in total, and at most once per index.
Both operations may be applied to the same index (each at most once, in either order).
Return the minimum possible sum of all elements of nums after any number of operations.
Example 1
Input: nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1
Output: 23
Explanation: Subtract 3 from 8 (it becomes 5) and halve 19 (it becomes 10): [2,5,3,10,3] sums to 23.
Example 2
Input: nums = [2,4,3], k = 3, op1 = 2, op2 = 1
Output: 3
Explanation: Halve 2 to 1; halve 4 to 2; subtract 3 from 3: [1,2,0].
Example 3
Input: nums = [5], k = 10, op1 = 1, op2 = 1
Output: 3
Explanation: 5 is below k, so only the halving applies: ceil(5 / 2) = 3.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 10^50 <= k <= 10^50 <= op1, op2 <= nums.length
Hints for Minimum Array Sum
Hint 1
Each index ends in one of four states: untouched, halved, reduced by
k, or both. The only coupling between indices is the two budgets.Hint 2
That is a knapsack with two capacities:
dp[a][b]= minimum sum of the processed prefix usingahalvings andbsubtractions.Hint 3
When both operations hit one index, the order matters: halving first needs
ceil(x / 2) >= k, subtracting first needsx >= k. Try both valid orders and keep the smaller result.
How to solve Minimum Array Sum
Every element independently chooses one of four outcomes, and the choices only interact through the two operation budgets. A DP over elements with the budgets used so far as the state explores all combinations in O(n · op1 · op2).
Approach
- Let
dp[a][b]be the minimum sum so far usingahalvings andbsubtractions; start withdp[0][0] = 0and everything else infinite. - For each
x, compute the four outcomes:x;ceil(x / 2);x - kifx >= k; and for both, the smaller ofceil(x / 2) - k(ifceil(x / 2) >= k) andceil((x - k) / 2)(ifx >= k). - Relax
ndpfrom every finitedp[a][b]with each outcome, adding 1 toaand/orbas the outcome uses them, never pastop1/op2. - Return the minimum over all
dp[a][b].
Why it works
Because each operation may be used at most once per index, an index's contribution depends only on which operations it received and in which order; the four outcomes (with the better order for "both") are exhaustive. Two prefixes with the same budget usage are interchangeable for the rest of the array, so keeping the minimum per (a, b) is exact.
Complexity
- Time —
O(n · op1 · op2) - Space —
O(op1 · op2)
Pitfalls
- Operation 1 rounds up:
ceil(x / 2) = (x + 1) / 2in integer arithmetic. - Subtracting before halving is only allowed when
x >= k; halving before subtracting only whenceil(x / 2) >= k. Either order can be the better one. - A greedy ("spend subtractions on the largest elements") fails because the two budgets compete for the same elements.
Reference solution
Python
from typing import List
def minArraySum(nums: List[int], k: int, op1: int, op2: int) -> int:
INF = float('inf')
dp = [[INF] * (op2 + 1) for _ in range(op1 + 1)]
dp[0][0] = 0
for x in nums:
half = (x + 1) // 2
sub = x - k if x >= k else None
both = None
if half >= k:
both = half - k
if x >= k:
v = (x - k + 1) // 2
both = v if both is None else min(both, v)
nd = [[INF] * (op2 + 1) for _ in range(op1 + 1)]
for a in range(op1 + 1):
for b in range(op2 + 1):
cur = dp[a][b]
if cur == INF:
continue
if cur + x < nd[a][b]:
nd[a][b] = cur + x
if a < op1 and cur + half < nd[a + 1][b]:
nd[a + 1][b] = cur + half
if sub is not None and b < op2 and cur + sub < nd[a][b + 1]:
nd[a][b + 1] = cur + sub
if both is not None and a < op1 and b < op2 and cur + both < nd[a + 1][b + 1]:
nd[a + 1][b + 1] = cur + both
dp = nd
return min(min(row) for row in dp)Java
public static int minArraySum(int[] nums, int k, int op1, int op2) {
final int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[op1 + 1][op2 + 1];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int x : nums) {
int half = (x + 1) / 2;
int sub = x >= k ? x - k : -1;
int both = -1;
if (half >= k) both = half - k;
if (x >= k) {
int v = (x - k + 1) / 2;
if (both < 0 || v < both) both = v;
}
int[][] nd = new int[op1 + 1][op2 + 1];
for (int[] row : nd) Arrays.fill(row, INF);
for (int a = 0; a <= op1; a++) {
for (int b = 0; b <= op2; b++) {
int cur = dp[a][b];
if (cur == INF) continue;
nd[a][b] = Math.min(nd[a][b], cur + x);
if (a < op1) nd[a + 1][b] = Math.min(nd[a + 1][b], cur + half);
if (sub >= 0 && b < op2) nd[a][b + 1] = Math.min(nd[a][b + 1], cur + sub);
if (both >= 0 && a < op1 && b < op2) nd[a + 1][b + 1] = Math.min(nd[a + 1][b + 1], cur + both);
}
}
dp = nd;
}
int best = INF;
for (int[] row : dp) for (int v : row) best = Math.min(best, v);
return best;
}C++
int minArraySum(vector<int>& nums, int k, int op1, int op2) {
const int INF = INT_MAX / 2;
vector<vector<int>> dp(op1 + 1, vector<int>(op2 + 1, INF));
dp[0][0] = 0;
for (int x : nums) {
int half = (x + 1) / 2;
int sub = x >= k ? x - k : -1;
int both = -1;
if (half >= k) both = half - k;
if (x >= k) {
int v = (x - k + 1) / 2;
if (both < 0 || v < both) both = v;
}
vector<vector<int>> nd(op1 + 1, vector<int>(op2 + 1, INF));
for (int a = 0; a <= op1; a++) {
for (int b = 0; b <= op2; b++) {
int cur = dp[a][b];
if (cur == INF) continue;
nd[a][b] = min(nd[a][b], cur + x);
if (a < op1) nd[a + 1][b] = min(nd[a + 1][b], cur + half);
if (sub >= 0 && b < op2) nd[a][b + 1] = min(nd[a][b + 1], cur + sub);
if (both >= 0 && a < op1 && b < op2) nd[a + 1][b + 1] = min(nd[a + 1][b + 1], cur + both);
}
}
dp = nd;
}
int best = INF;
for (auto& row : dp) for (int v : row) best = min(best, v);
return best;
}JavaScript
var minArraySum = function(nums, k, op1, op2) {
var INF = Infinity;
var grid = function() {
var g = [];
for (var a = 0; a <= op1; a++) g.push(new Array(op2 + 1).fill(INF));
return g;
};
var dp = grid();
dp[0][0] = 0;
for (var i = 0; i < nums.length; i++) {
var x = nums[i];
var half = Math.floor((x + 1) / 2);
var sub = x >= k ? x - k : -1;
var both = -1;
if (half >= k) both = half - k;
if (x >= k) {
var v = Math.floor((x - k + 1) / 2);
if (both < 0 || v < both) both = v;
}
var nd = grid();
for (var a = 0; a <= op1; a++) {
for (var b = 0; b <= op2; b++) {
var cur = dp[a][b];
if (cur === INF) continue;
if (cur + x < nd[a][b]) nd[a][b] = cur + x;
if (a < op1 && cur + half < nd[a + 1][b]) nd[a + 1][b] = cur + half;
if (sub >= 0 && b < op2 && cur + sub < nd[a][b + 1]) nd[a][b + 1] = cur + sub;
if (both >= 0 && a < op1 && b < op2 && cur + both < nd[a + 1][b + 1]) nd[a + 1][b + 1] = cur + both;
}
}
dp = nd;
}
var best = INF;
for (var p = 0; p <= op1; p++) for (var q = 0; q <= op2; q++) if (dp[p][q] < best) best = dp[p][q];
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming