Skip to content

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

Β 

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

Example 2:

Input: nums = [2,4,3], k = 3, op1 = 2, op2 = 1

Output: 3

Explanation:

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

Β 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 105
  • 0 <= k <= 105
  • 0 <= 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}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
}

Comments