Welcome to Subscribe On Youtube
3366. Minimum Array Sum
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
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
Solutions
Solution 1: Dynamic Programming
For convenience, we denote the given $k$ as $d$.
Next, we define $f[i][j][k]$ to represent the minimum sum of the first $i$ numbers using $j$ operations of type 1 and $k$ operations of type 2. Initially, $f[0][0][0] = 0$, and the rest $f[i][j][k] = +\infty$.
Consider how to transition the state for $f[i][j][k]$. We can enumerate the $i$-th number $x$ and then consider the impact of $x$ on $f[i][j][k]$:
- If $x$ does not use operation 1 or operation 2, then $f[i][j][k] = f[i-1][j][k] + x$;
- If $j \gt 0$, then we can use operation 1. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k] + \lceil \frac{x+1}{2} \rceil)$;
- If $k \gt 0$ and $x \geq d$, then we can use operation 2. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j][k-1] + (x - d))$;
- If $j \gt 0$ and $k \gt 0$, then we can use both operation 1 and operation 2. If we use operation 1 first, then $x$ becomes $\lceil \frac{x+1}{2} \rceil$. If $x \geq d$, then we can use operation 2. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \lceil \frac{x+1}{2} \rceil - d)$. If we use operation 2 first, then $x$ becomes $x - d$. If $x \geq d$, then we can use operation 1. In this case, $f[i][j][k] = \min(f[i][j][k], f[i-1][j-1][k-1] + \lceil \frac{x-d+1}{2} \rceil)$.
The final answer is $\min_{j=0}^{op1} \min_{k=0}^{op2} f[n][j][k]$. If it is $+\infty$, then output $-1$.
The time complexity is $O(n \times \textit{op1} \times \textit{op2})$, and the space complexity is $O(n \times \textit{op1} \times \textit{op2})$. Here, $n$ is the length of the array $\textit{nums}$.
-
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; } } -
class Solution { public: int minArraySum(vector<int>& nums, int d, int op1, int op2) { int n = nums.size(); int f[n + 1][op1 + 1][op2 + 1]; memset(f, 0x3f, sizeof f); 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] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) / 2); } if (k > 0 && x >= d) { f[i][j][k] = 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] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (y - d)); } if (x >= d) { f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) / 2); } } } } } int ans = INT_MAX; for (int j = 0; j <= op1; ++j) { for (int k = 0; k <= op2; ++k) { ans = min(ans, f[n][j][k]); } } return ans; } }; -
class Solution: def minArraySum(self, nums: List[int], d: int, op1: int, op2: int) -> int: n = len(nums) f = [[[inf] * (op2 + 1) for _ in range(op1 + 1)] for _ in range(n + 1)] f[0][0][0] = 0 for i, x in enumerate(nums, 1): for j in range(op1 + 1): for k in range(op2 + 1): f[i][j][k] = f[i - 1][j][k] + x if j > 0: f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + (x + 1) // 2) if k > 0 and x >= d: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] + (x - d)) if j > 0 and k > 0: y = (x + 1) // 2 if y >= d: f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + y - d) if x >= d: f[i][j][k] = min( f[i][j][k], f[i - 1][j - 1][k - 1] + (x - d + 1) // 2 ) ans = inf for j in range(op1 + 1): for k in range(op2 + 1): ans = min(ans, f[n][j][k]) return ans -
func minArraySum(nums []int, d int, op1 int, op2 int) int { n := len(nums) const inf = int(1e9) f := make([][][]int, n+1) for i := range f { f[i] = make([][]int, op1+1) for j := range f[i] { f[i][j] = make([]int, op2+1) for k := range f[i][j] { f[i][j][k] = inf } } } f[0][0][0] = 0 for i := 1; i <= n; i++ { x := nums[i-1] for j := 0; j <= op1; j++ { for k := 0; k <= op2; k++ { f[i][j][k] = f[i-1][j][k] + x if j > 0 { f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k]+(x+1)/2) } if k > 0 && x >= d { f[i][j][k] = min(f[i][j][k], f[i-1][j][k-1]+(x-d)) } if j > 0 && k > 0 { y := (x + 1) / 2 if y >= d { f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k-1]+(y-d)) } if x >= d { f[i][j][k] = min(f[i][j][k], f[i-1][j-1][k-1]+(x-d+1)/2) } } } } } ans := inf for j := 0; j <= op1; j++ { for k := 0; k <= op2; k++ { ans = min(ans, f[n][j][k]) } } return ans } -
function minArraySum(nums: number[], d: number, op1: number, op2: number): number { const n = nums.length; const inf = Number.MAX_SAFE_INTEGER; const f: number[][][] = Array.from({ length: n + 1 }, () => Array.from({ length: op1 + 1 }, () => Array(op2 + 1).fill(inf)), ); f[0][0][0] = 0; for (let i = 1; i <= n; i++) { const x = nums[i - 1]; for (let j = 0; j <= op1; j++) { for (let k = 0; k <= op2; k++) { f[i][j][k] = Math.min(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] + Math.floor((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) { const y = Math.floor((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] + Math.floor((x - d + 1) / 2), ); } } } } } let ans = inf; for (let j = 0; j <= op1; j++) { for (let l = 0; l <= op2; l++) { ans = Math.min(ans, f[n][j][l]); } } return ans; }