Facebook Pixel

3366. Minimum Array Sum

MediumArrayDynamic Programming
Leetcode Link

Problem Description

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.

Intuition

To solve this problem, the challenge is to minimize the sum of the array nums by performing a limited number of two types of operations on the elements. The operations are restricted by their respective maximum permissible counts (op1 and op2), creating a need for strategic application of these operations.

The key insight here is to use dynamic programming (DP) to systematically explore the various combinations of operations applied to each element of the array. We define a DP state f[i][j][k] that represents the minimum sum obtained using the first i elements of the array, with exactly j applications of Operation 1, and k applications of Operation 2.

Steps and Decisions:

  1. Initialization:

    • Start with f[0][0][0] = 0, meaning there is no sum when no elements are processed.
    • Other states are initialized to a large value (+infinity) to ensure they naturally find the minimum value when processed.

  2. State Transitions:

    • For each element x in nums, you have a decision tree based on applying operations:
      • If no operations are applied: [ f[i][j][k] = f[i-1][j][k] + x ]
      • If Operation 1 is applied (and j > 0): [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k] + \left\lceil \frac{x}{2} \right\rceil) ]
      • If Operation 2 is applied (and k > 0 and x \geq k): [ f[i][j][k] = \min(f[i][j][k], f[i-1][j][k-1] + (x - k)) ]
      • If both operations are applicable:
        • Apply Operation 1 first, then Operation 2 (if conditions allow), result after both: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \left\lceil \frac{x}{2} \right\rceil - k) ]
        • Apply Operation 2 first, then Operation 1, result after both: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \left\lceil \frac{x-k}{2} \right\rceil) ]

  3. Result Extraction:

    • The answer will be the minimum value among all possible states f[n][j][k] with j and k in their respective allowable ranges. If the result is +infinity, it means no valid operation sequence was possible and traditionally you might return -1.

The structured approach ensures that we consider all practical ways of applying each operation, taking into account their limited availability to achieve the optimal minimal sum.

Learn more about Dynamic Programming patterns.

Solution Approach

Dynamic Programming

The solution uses dynamic programming to find the optimal way to apply operations on the array nums while minimizing the sum of its elements. We define a 3D DP table f[i][j][k] where:

  • i represents the number of elements considered from the array.
  • j is the count of Operation 1 applied.
  • k is the count of Operation 2 applied.

The initial DP state is set as follows:

  • f[0][0][0] = 0, representing zero sum when no elements are included.
  • All other states are initialized to infinity (inf) to facilitate finding the minimal value naturally by comparing with very large initial values.

For each element x from nums, calculate transitions:

  1. No Operation:

    • If applying no operation to x, update: [ f[i][j][k] = f[i-1][j][k] + x ]

  2. Operation 1 (Division by 2):

    • If it is possible to apply Operation 1 (j > 0), update: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k] + \left\lceil \frac{x}{2} \right\rceil) ]

  3. Operation 2 (Subtraction of k):

    • If applying Operation 2 is feasible (k > 0 and x \geq k), update: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j][k-1] + (x - k)) ]

  4. Both Operations:

    • Applying Operation 1 first followed by Operation 2 where applicable:

      • If the new resulting number after Operation 1 is greater or equal to k: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \left\lceil \frac{x}{2} \right\rceil - k) ]

    • Alternatively, applying Operation 2 first followed by Operation 1: [ f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \left\lceil \frac{x-k}{2} \right\rceil) ]

The result is the minimal value found in the DP table for f[len(nums)][j][k], iterating over all permissible values of j and k.

By carefully managing transitions and handling the conditional applications of operations, this approach efficiently leverages dynamic programming to calculate the smallest possible sum of the array elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the dynamic programming approach described. Assume we have the following inputs:

  • nums = [10, 20]
  • k = 5
  • op1 = 1
  • op2 = 1

We want to minimize the sum of the elements in nums by applying at most 1 of each operation.

Step 1: Initialization

We initialize our DP table f where f[0][0][0] = 0 and all other states are set to infinity. This represents the sum with no elements processed and no operations applied.

Step 2: Process Each Element

  1. Element 10:

    • Without any operation: f[1][0][0] = f[0][0][0] + 10 = 10
    • Operation 1 (Division by 2): [ f[1][1][0] = \min(f[1][1][0], f[0][0][0] + \lceil 10/2 \rceil) = 5 ]
    • Operation 2 (Subtract k): [ f[1][0][1] = \min(f[1][0][1], f[0][0][0] + (10 - 5)) = 5 ]
    • Both Operations:
      • Apply Operation 1 first, then Operation 2: [ f[1][1][1] = \min(f[1][1][1], f[0][0][0] + \lceil 10/2 \rceil - 5) = \inf \text{ (not feasible)} ]
      • Apply Operation 2 first, then Operation 1: [ f[1][1][1] = \min(f[1][1][1], f[0][0][0] + \lceil (10-5)/2 \rceil) = 3 ]

  2. Element 20:

    • Without any operation: f[2][0][0] = f[1][0][0] + 20 = 30
    • Operation 1 (Division by 2): For f[1][1][0]: [ f[2][1][0] = \min(f[2][1][0], f[1][1][0] + \lceil 20/2 \rceil) = 15 ]
    • Operation 2 (Subtract k): For f[1][0][1]: [ f[2][0][1] = \min(f[2][0][1], f[1][0][1] + (20 - 5)) = 20 ]
    • Both Operations:
      • Apply Operation 1 first, then Operation 2: Using f[1][1][0]: [ f[2][1][1] = \min(f[2][1][1], f[1][1][0] + \lceil 20/2 \rceil - 5) = 10 ]
      • Apply Operation 2 first, then Operation 1: Using f[1][0][1]: [ f[2][1][1] = \min(f[2][1][1], f[1][0][1] + \lceil (20-5)/2 \rceil) = 13 ]

Step 3: Result Extraction

The minimum value among f[2][j][k] for all possible j and k is 10 for f[2][1][1].

This demonstrates how the dynamic programming solution navigates possible operation applications to minimize the sum effectively.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minArraySum(self, nums: List[int], d: int, op1: int, op2: int) -> int:
6        n = len(nums)
7        # Initialize a 3D list 'f' to store the minimum sum, filled with infinity.
8        dp = [[[inf] * (op2 + 1) for _ in range(op1 + 1)] for _ in range(n + 1)]
9        dp[0][0][0] = 0  # Base case: zero operations leads to a sum of zero.
10      
11        for i, num in enumerate(nums, start=1):  # Traverse each number in the list along with its index.
12            for j in range(op1 + 1):
13                for k in range(op2 + 1):
14                    # Case 1: No operations applied to current number.
15                    dp[i][j][k] = dp[i - 1][j][k] + num
16                  
17                    # Case 2: Apply the first operation.
18                    if j > 0:
19                        dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k] + (num + 1) // 2)
20                  
21                    # Case 3: Apply the second operation if num is not less than d.
22                    if k > 0 and num >= d:
23                        dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1] + (num - d))
24                  
25                    # Both operations applied.
26                    if j > 0 and k > 0:
27                        halved_num = (num + 1) // 2
28                        # Applying both operations if halved number is not less than d.
29                        if halved_num >= d:
30                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k - 1] + halved_num - d)
31                        # Applying both operations directly if num is not less than d.
32                        if num >= d:
33                            dp[i][j][k] = min(
34                                dp[i][j][k], dp[i - 1][j - 1][k - 1] + (num - d + 1) // 2
35                            )
36      
37        # Find the minimum sum possible after all operations.
38        minimum_sum = inf
39        for j in range(op1 + 1):
40            for k in range(op2 + 1):
41                minimum_sum = min(minimum_sum, dp[n][j][k])
42      
43        return minimum_sum
44
1import java.util.Arrays;
2
3class Solution {
4  
5    // Method to find minimum array sum with given operations
6    public int minArraySum(int[] nums, int d, int op1, int op2) {
7        int n = nums.length;
8        int[][][] dp = new int[n + 1][op1 + 1][op2 + 1];
9        final int INF = 1 << 29;
10      
11        // Initialize dp matrix with a large value (representing infinity)
12        for (int[][] matrix2D : dp) {
13            for (int[] row : matrix2D) {
14                Arrays.fill(row, INF);
15            }
16        }
17      
18        // Base case: no operations performed on an empty array
19        dp[0][0][0] = 0;
20      
21        for (int i = 1; i <= n; ++i) {
22            int currentNum = nums[i - 1];
23          
24            for (int j = 0; j <= op1; ++j) {
25                for (int k = 0; k <= op2; ++k) {
26                  
27                    // Case 1: No operations used
28                    dp[i][j][k] = dp[i - 1][j][k] + currentNum;
29                  
30                    // Case 2: Use one `op1` operation
31                    if (j > 0) {
32                        dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][k] + (currentNum + 1) / 2);
33                    }
34                  
35                    // Case 3: Use one `op2` operation if number is greater than or equal to d
36                    if (k > 0 && currentNum >= d) {
37                        dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k - 1] + (currentNum - d));
38                    }
39
40                    // Case 4: Use both `op1` and `op2` operations
41                    if (j > 0 && k > 0) {
42                        int halfNumRounded = (currentNum + 1) / 2;
43                        if (halfNumRounded >= d) {
44                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][k - 1] + (halfNumRounded - d));
45                        }
46                        if (currentNum >= d) {
47                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][k - 1] + (currentNum - d + 1) / 2);
48                        }
49                    }
50                }
51            }
52        }
53      
54        // Find the minimum sum achieved with any combination of operations
55        int result = INF;
56        for (int j = 0; j <= op1; ++j) {
57            for (int k = 0; k <= op2; ++k) {
58                result = Math.min(result, dp[n][j][k]);
59            }
60        }
61        return result;
62    }
63}
64
1class Solution {
2public:
3    int minArraySum(vector<int>& nums, int d, int op1, int op2) {
4        int n = nums.size();
5      
6        // Dynamic programming table initialized to infinity
7        int f[n + 1][op1 + 1][op2 + 1];
8        memset(f, 0x3f, sizeof(f));  // Fill array with a large number, simulating infinity
9      
10        // Base case: no operations needed, sum is 0
11        f[0][0][0] = 0;
12      
13        // Iterate over each element in nums
14        for (int i = 1; i <= n; ++i) {
15            int currentVal = nums[i - 1];  // Current element in the nums vector
16          
17            // Consider all combinations of operations
18            for (int j = 0; j <= op1; ++j) {
19                for (int k = 0; k <= op2; ++k) {
20                  
21                    // Use no operation, add current value to the cumulative sum
22                    f[i][j][k] = f[i - 1][j][k] + currentVal;
23                  
24                    // Use the first type of operation, if possible
25                    if (j > 0) {
26                        // Apply (x + 1) / 2 operation
27                        f[i][j][k] = std::min(f[i][j][k], f[i - 1][j - 1][k] + (currentVal + 1) / 2);
28                    }
29                  
30                    // Use the second type of operation, if applicable
31                    if (k > 0 && currentVal >= d) {
32                        // Apply (x - d) operation
33                        f[i][j][k] = std::min(f[i][j][k], f[i - 1][j][k - 1] + (currentVal - d));
34                    }
35                  
36                    // Use both operations, if possible
37                    if (j > 0 && k > 0) {
38                        // Calculate value after performing the first operation
39                        int reducedValue = (currentVal + 1) / 2;
40                        // Apply second operation on reduced value
41                        if (reducedValue >= d) {
42                            f[i][j][k] = std::min(f[i][j][k], f[i - 1][j - 1][k - 1] + (reducedValue - d));
43                        }
44                        // Another combination of both operations
45                        if (currentVal >= d) {
46                            f[i][j][k] = std::min(f[i][j][k], f[i - 1][j - 1][k - 1] + (currentVal - d + 1) / 2);
47                        }
48                    }
49                }
50            }
51        }
52      
53        // Find the minimum sum possible with any combination of operations
54        int answer = INT_MAX;
55        for (int j = 0; j <= op1; ++j) {
56            for (int k = 0; k <= op2; ++k) {
57                answer = std::min(answer, f[n][j][k]);
58            }
59        }
60      
61        return answer;  // Return the minimum possible sum
62    }
63};
64
1function minArraySum(nums: number[], d: number, op1: number, op2: number): number {
2    const n = nums.length;  // Length of input array nums
3    const inf = Number.MAX_SAFE_INTEGER;  // Use a large number to represent infinity
4
5    // 3D array for dynamic programming, initialized to infinity
6    const f: number[][][] = Array.from({ length: n + 1 }, () =>
7        Array.from({ length: op1 + 1 }, () => Array(op2 + 1).fill(inf)),
8    );
9    f[0][0][0] = 0;  // Base case: no elements, no operations used, sum is zero
10
11    // Iterate over each element in nums
12    for (let i = 1; i <= n; i++) {
13        const x = nums[i - 1];  // Current element in the array
14        // Iterate over possible usage of operation 1
15        for (let j = 0; j <= op1; j++) {
16            // Iterate over possible usage of operation 2
17            for (let k = 0; k <= op2; k++) {
18                // Case 1: No operations used on current element
19                f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + x);
20              
21                // Case 2: Use operation 1 (halve operation)
22                if (j > 0) {
23                    const halved = Math.floor((x + 1) / 2);
24                    f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + halved);
25                }
26              
27                // Case 3: Use operation 2 (subtract d if x >= d)
28                if (k > 0 && x >= d) {
29                    f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k - 1] + (x - d));
30                }
31              
32                // Case 4: Use both operations if possible
33                if (j > 0 && k > 0) {
34                    const halved = Math.floor((x + 1) / 2);
35                    if (halved >= d) {
36                        f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + (halved - d));
37                    }
38                    if (x >= d) {
39                        const afterBothOps = Math.floor((x - d + 1) / 2);
40                        f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + afterBothOps);
41                    }
42                }
43            }
44        }
45    }
46
47    let ans = inf;  // To store the minimum sum
48    // Iterate over all possible combinations of operations and find the minimum sum
49    for (let j = 0; j <= op1; j++) {
50        for (let l = 0; l <= op2; l++) {
51            ans = Math.min(ans, f[n][j][l]);
52        }
53    }
54    return ans;  // Return the minimum sum obtained
55}
56

Time and Space Complexity

The time complexity of the code is O(n \times \textit{op1} \times \textit{op2}), where n is the length of the array nums, op1 is the number of operations for adding half, and op2 is the number of operations for reducing by d. This complexity arises from the three nested loops iterating over i from 1 to n, j from 0 to op1, and k from 0 to op2.

The space complexity of the code is also O(n \times \textit{op1} \times \textit{op2}), due to the 3D list f which has dimensions (n + 1) \times (\textit{op1} + 1) \times (\textit{op2} + 1).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More