LeetCode-in-Java

3987. Minimum Total Cost to Process All Elements

Medium

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

Solution

public class Solution {
    public int minimumCost(int[] nums, int k) {
        long sum = 0L;
        int mod = 1000000007;
        for (int num : nums) {
            sum = sum + num;
        }
        if (sum < k) {
            return 0;
        }
        long kRequired;
        if (sum % k == 0) {
            kRequired = sum / k;
        } else {
            kRequired = sum / k + 1;
        }
        return (int) func(kRequired - 1, mod);
    }

    private long func(long n, int mod) {
        long ans = ((n % mod) * ((n + 1) % mod)) % mod;
        ans = (ans * 500000004) % mod;
        return ans;
    }
}

This site is open source. Improve this page.