Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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);
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• 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)
  }
  
  

• 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);
  }
  
  

All Problems

All Solutions