Skip to content

3987. Minimum Total Cost to Process All Elements

Description

You are given an integer array nums and an integer k.

Initially, you have k units of resources.

You must process the elements of nums from left to right. To process the ith element, you need nums[i] resources.

If your available resources are less than nums[i], you may perform an operation that increases your available resources by k. The value of k is fixed and does not change throughout the process. The first such operation incurs a cost of 1, the second incurs a cost of 2, and so on.

After processing the ith element, your available resources decrease by nums[i].

Return an integer denoting the minimum total cost required to process all elements. Since the answer may be very large, return it modulo 109 + 7.

Β 

Example 1:

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

Output: 3

Explanation:

  • After processing nums[0], we have 4 - 1 = 3 units of resources left.
  • After processing nums[1], we have 3 - 2 = 1 unit of resources left.
  • Since nums[2] = 3 and only 1 unit of resources is available, we perform the first operation costing 1. After processing nums[2], we have 1 + 4 - 3 = 2 units of resources left.
  • Since nums[3] = 4 and only 2 units of resources are available, we perform the second operation costing 2, to have 2 + 4 = 6 units of resources,Β which is enough toΒ process nums[3].
  • Thus, the total cost is 1 + 2 = 3.

Example 2:

Input: nums = [1,1,7,14], k = 4

Output: 15

Explanation:

  • After processing nums[0], we have 4 - 1 = 3 units of resources left.
  • After processing nums[1], we have 3 - 1 = 2 units of resources left.
  • Since nums[2] = 7 and only 2 units of resources are available, we perform two operations costing 1 + 2 = 3. After processing nums[2], we have 2 + 4 + 4 - 7 = 3 units of resources left.
  • Since nums[3] = 14 and only 3 units of resources are available, we perform three operations costing 3 + 4 + 5 = 12, to have 3 + 4 + 4 + 4 = 15 units of resources,Β which is enough toΒ process nums[3].
  • Thus, the total cost is 3 + 12 = 15.

Example 3:

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

Output: 0

Explanation:

To process all elements, we can use the initial 10 units of resources without performing any operations. Thus, the total cost required is 0.

Β 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Solutions

Solution 1: Simulation

The \(i\)-th operation costs \(i\), so if we perform \(\textit{cnt}\) operations in total, the total cost is \(1 + 2 + \cdots + \textit{cnt} = \dfrac{\textit{cnt}(\textit{cnt}+1)}{2}\). Minimizing the total cost is equivalent to minimizing the number of operations.

Simulate the process from left to right. Maintain the current available resources \(\textit{cur}\) (initially \(k\)) and the number of operations performed \(\textit{cnt}\). When processing an element \(x\):

  • If \(\textit{cur} \ge x\), simply subtract \(x\);
  • Otherwise, perform \(m = \left\lceil\dfrac{x - \textit{cur}}{k}\right\rceil\) more operations to increase resources by \(m \times k\), then subtract \(x\).

After the traversal, compute the triangular number of \(\textit{cnt}\) and take the result modulo \(10^9 + 7\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minimumCost(self, nums: list[int], k: int) -> int:
        cnt = 0
        cur = k
        mod = 10**9 + 7
        for x in nums:
            diff = x - cur
            if diff > 0:
                m = (diff + k - 1) // k
                cur += m * k
                cnt += m
            cur -= x
        cnt %= mod
        return (1 + cnt) * cnt // 2 % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumCost(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        long cnt = 0;
        long cur = k;

        for (int x : nums) {
            long diff = (long) x - cur;
            if (diff > 0) {
                long m = (diff + k - 1L) / k;
                cur += m * (long) k;
                cnt += m;
            }
            cur -= x;
        }

        cnt %= MOD;
        return (int) ((cnt + 1) * cnt / 2 % MOD);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumCost(vector<int>& nums, int k) {
        const int MOD = 1'000'000'007;
        long long cnt = 0;
        long long cur = k;

        for (int x : nums) {
            long long diff = (long long) x - cur;
            if (diff > 0) {
                long long m = (diff + k - 1LL) / k;
                cur += m * k;
                cnt += m;
            }
            cur -= x;
        }

        cnt %= MOD;
        return (cnt + 1) * cnt / 2 % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minimumCost(nums []int, k int) int {
    const mod int64 = 1_000_000_007
    var cnt int64
    cur := int64(k)

    for _, x := range nums {
        diff := int64(x) - cur
        if diff > 0 {
            m := (diff + int64(k) - 1) / int64(k)
            cur += m * int64(k)
            cnt += m
        }
        cur -= int64(x)
    }

    cnt %= mod
    return int((cnt + 1) * cnt / 2 % mod)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function minimumCost(nums: number[], k: number): number {
    const MOD = 1000000007n;
    let cnt = 0n;
    let cur = BigInt(k);
    const K = BigInt(k);

    for (const x of nums) {
        const diff = BigInt(x) - cur;
        if (diff > 0n) {
            const m = (diff + K - 1n) / K;
            cur += m * K;
            cnt += m;
        }
        cur -= BigInt(x);
    }

    cnt %= MOD;
    return Number((((cnt + 1n) * cnt) / 2n) % MOD);
}

Comments