In this guide, you will get 3366. Minimum Array Sum LeetCode Solution with the best time and space complexity. The solution to Minimum Array Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
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.
Time Complexity: O(k \cdot \texttt{op1} \cdot \texttt{op2})
Space Complexity: O(k \cdot \texttt{op1} \cdot \texttt{op2})
3366. Minimum Array Sum LeetCode Solution in C++
class Solution {
public:
int minArraySum(vector<int>& nums, int k, int op1, int op2) {
vector<vector<vector<int>>> mem(
nums.size(),
vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, INT_MAX)));
return minArraySum(nums, 0, op1, op2, k, mem);
}
private:
// Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
// `op2` operations of op2.
int minArraySum(const vector<int>& nums, int i, int op1, int op2, int k,
vector<vector<vector<int>>>& mem) {
if (i == nums.size())
return 0;
if (mem[i][op1][op2] != INT_MAX)
return mem[i][op1][op2];
int res = nums[i] + minArraySum(nums, i + 1, op1, op2, k, mem);
if (op1 > 0)
res = min(res, (nums[i] + 1) / 2 +
minArraySum(nums, i + 1, op1 - 1, op2, k, mem));
if (op2 > 0 && nums[i] >= k)
res = min(res,
nums[i] - k + minArraySum(nums, i + 1, op1, op2 - 1, k, mem));
if (op1 > 0 && op2 > 0) {
if ((nums[i] + 1) / 2 >= k)
res = min(res, (nums[i] + 1) / 2 - k +
minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
if (nums[i] >= k)
res = min(res, (nums[i] - k + 1) / 2 +
minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
}
return mem[i][op1][op2] = res;
}
}; /* code provided by PROGIEZ */
3366. Minimum Array Sum LeetCode Solution in Java
class Solution {
public int minArraySum(int[] nums, int k, int op1, int op2) {
Integer[][][] mem = new Integer[nums.length][op1 + 1][op2 + 1];
return minArraySum(nums, 0, op1, op2, k, mem);
}
// Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
// `op2` operations of op2.
private int minArraySum(int[] nums, int i, int op1, int op2, int k, Integer[][][] mem) {
if (i == nums.length)
return 0;
if (mem[i][op1][op2] != null)
return mem[i][op1][op2];
int res = nums[i] + minArraySum(nums, i + 1, op1, op2, k, mem);
if (op1 > 0)
res = Math.min(res, (nums[i] + 1) / 2 + minArraySum(nums, i + 1, op1 - 1, op2, k, mem));
if (op2 > 0 && nums[i] >= k)
res = Math.min(res, nums[i] - k + minArraySum(nums, i + 1, op1, op2 - 1, k, mem));
if (op1 > 0 && op2 > 0) {
if ((nums[i] + 1) / 2 >= k)
res = Math.min(res,
(nums[i] + 1) / 2 - k + minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
if (nums[i] >= k)
res = Math.min(res,
(nums[i] - k + 1) / 2 + minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
}
return mem[i][op1][op2] = res;
}
} // code provided by PROGIEZ
3366. Minimum Array Sum LeetCode Solution in Python
class Solution:
def minArraySum(self, nums: list[int], k: int, op1: int, op2: int) -> int:
@functools.lru_cache(None)
def dp(i: int, op1: int, op2: int) -> int:
"""
Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
`op2` operations of op2.
"""
if i == len(nums):
return 0
res = nums[i] + dp(i + 1, op1, op2)
if op1 > 0:
res = min(res, (nums[i] + 1) // 2 + dp(i + 1, op1 - 1, op2))
if op2 > 0 and nums[i] >= k:
res = min(res, nums[i] - k + dp(i + 1, op1, op2 - 1))
if op1 > 0 and op2 > 0:
if (nums[i] + 1) // 2 >= k:
res = min(res, (nums[i] + 1) // 2 - k + dp(i + 1, op1 - 1, op2 - 1))
if nums[i] >= k:
res = min(res, (nums[i] - k + 1) // 2 + dp(i + 1, op1 - 1, op2 - 1))
return res
return dp(0, op1, op2) # code by PROGIEZ
