Minimum Array Sum

Medium
1670.

Minimum Array Sum

Minimum Array Sum is a medium coding problem on arrays and dynamic programming, asked in Google interviews.

You are given an integer array nums and three integers k, op1 and op2. Two operations are available:

  • Operation 1: pick an index i and replace nums[i] with nums[i] / 2 rounded up. You may do this at most op1 times in total, and at most once per index.
  • Operation 2: pick an index i with nums[i] >= k and subtract k from it. You may do this at most op2 times 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 <= 100
  • 0 <= nums[i] <= 10^5
  • 0 <= k <= 10^5
  • 0 <= op1, op2 <= nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} op1
 * @param {number} op2
 * @return {number}
 */
var minArraySum = function(nums, k, op1, op2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 i and replace nums[i] with nums[i] / 2 rounded up. You may do this at most op1 times in total, and at most once per index.
  • Operation 2: pick an index i with nums[i] >= k and subtract k from it. You may do this at most op2 times 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 <= 100
  • 0 <= nums[i] <= 10^5
  • 0 <= k <= 10^5
  • 0 <= op1, op2 <= nums.length

Hints for Minimum Array Sum

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

  2. Hint 2

    That is a knapsack with two capacities: dp[a][b] = minimum sum of the processed prefix using a halvings and b subtractions.

  3. Hint 3

    When both operations hit one index, the order matters: halving first needs ceil(x / 2) >= k, subtracting first needs x >= 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

  1. Let dp[a][b] be the minimum sum so far using a halvings and b subtractions; start with dp[0][0] = 0 and everything else infinite.
  2. For each x, compute the four outcomes: x; ceil(x / 2); x - k if x >= k; and for both, the smaller of ceil(x / 2) - k (if ceil(x / 2) >= k) and ceil((x - k) / 2) (if x >= k).
  3. Relax ndp from every finite dp[a][b] with each outcome, adding 1 to a and/or b as the outcome uses them, never past op1/op2.
  4. 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) / 2 in integer arithmetic.
  • Subtracting before halving is only allowed when x >= k; halving before subtracting only when ceil(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