Minimum Decrements to Make an Array at Most Zero Such That All Array Elements Are Cyclically Decremented After a Number is Reduced to Zero

Introduction

Ninja is going to take admission to a coding academy. For admission to the academy, he must pass the assessment given by the academy. In the assessment, he has given a circular array ‘ARR’ and an array ‘COST’ of length ‘N’. Being a friend of a ninja, you want to help him pass the assessment.

The problem we will be discussing today is the standard greedy algorithm problem. Greedy algorithm based-coding problems are widely asked in coding contests and various coding interviews.

The Problem Statement

You are given a circular array ‘ARR’ and ‘COST’ of size ‘N’. Your task is to find the minimum operations required to make all the elements of an array equal to 0. In one operation, you will do the following:

1. Decrement the value of any index ‘i’ by one.
2. If the value of index ‘i’ becomes 0, then decrement ‘ARR[i + 1]’ by ‘COST[i]’ and ‘ARR[i + 2]’ by ‘COST[i + 1]’ and so on. 

Note: If the value of any index ‘I’ of array ‘ARR’ is less than 0, then it will be considered as 0.

Example

Let ‘ARR’ = {5, 2, 3, 8} and ‘COST’ = {10, 10, 10, 10}.

Then the minimum operations required to make all the elements of ‘ARR’ equal to zero is 2.

Decrement the ‘ARR[1]’ twice then ‘ARR[1]’ equal to zero and ‘ARR[2]’ = -7, ‘ARR[3]’ = -2,  ‘ARR[0]’ =  -5.

All the negative values are considered as 0. Hence, the minimum number of operations required to make all the elements equal to zero is 2.

Also see, Euclid GCD Algorithm

Approach

After analyzing the above example, we can conclude that:

• If we decrement any value in the array, then all the remaining elements, say index ‘i’ of the array, are decremented by ‘ARR[i + 1]’ - max(0, ‘ARR[i + 1]’ - ‘COST[i]’).

We will extend the above observation to find our result.

Algorithm

The algorithm for the above problem is as follows:

• Declare and define the function ‘minimumOperations(‘ARR ’, ‘COST’, ‘N’)’ which takes array ‘ARR’, ‘COST’ and ‘N’ as a parameter. In this function do the following:
  • Declare ‘ANS’ = 0 to store the final answer.
  • Declare ‘MINIMUM’ = INT_MAX to store the minimum value to reach any index value to 0 among all the indexes.
  • Iterate loop for 0 to ‘N’ :
    • Create variable ‘INDEX’ = (‘i’+ 1) % ‘N’.
    • If ‘ARR[INDEX]’ < ‘COST[i]’:
    • ‘MINIMUM’= min(‘MINIMUM’, ‘ARR[INDEX]’).
    • Else :
    • ‘ANS’ += max(0, ‘ARR[INDEX]’ - ‘COST[i]’).
    • ‘MINIMUM’= min(‘MINIMUM ’, ‘COST[INDEX]’).
  • ‘ANS’ += ’MINIMUM’.
  • Return ‘ANS’.
• Call the above function in the main function.

Program

​​#include <iostream>
#include <vector>
using namespace std;

int minimumOperations(vector<int> &arr, vector<int> &cost, int n)
{
   // Declare variable 'ANS' to store the final answer.
   int ans = 0;

   // Declare variable to find the minimum operations.
   int minimum = 1000000;

   for (int i = 0; i < n; i++)
   {
       // Index under consideration.
       int index = (i + 1) % n;
       if (arr[index] < cost[i])
       {
           minimum = min(minimum, arr[index]);
       }
       else
       {
           ans = ans + max(0, arr[index] - cost[i]);
           minimum = min(minimum, cost[i]);
       }
   }

   // Add minimum in the answer.
   ans = ans + minimum;
   return ans;
}

int main()
{

   // Declare variable 'N', i.e., no. of elements in the array.
   int n;
   cin >> n;

   // Taking array 'ARR' and 'COST' as an input.
   vector<int> arr(n), cost(n);
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }
   for (int i = 0; i < n; i++)
   {
       cin >> cost[i];
   }

   // Calling function 'minimumOperations()'.
   cout << minimumOperations(arr, cost, n);
   return 0;
}

Input

3
3 5 2
23 11 45

Output

2

Time Complexity

O(N), where ‘N’ is the size of the array.

Traversing all the elements in the array takes only O(N). Hence its time complexity is O(N).

Space Complexity

O(1).

As we didn’t use extra space except for a few variables.