LeetCode in Kotlin

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

class Solution {
    fun minimumCost(nums: IntArray, k: Int): Int {
        var sum = 0L
        val mod = 1000000007
        for (num in nums) {
            sum = sum + num
        }
        if (sum < k) {
            return 0
        }
        val kRequired: Long
        if (sum % k == 0L) {
            kRequired = sum / k
        } else {
            kRequired = sum / k + 1
        }
        return func(kRequired - 1, mod).toInt()
    }

    private fun func(n: Long, mod: Int): Long {
        var ans = ((n % mod) * ((n + 1) % mod)) % mod
        ans = (ans * 500000004) % mod
        return ans
    }
}

This site is open source. Improve this page.