Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
1.1.
Example
2.
Approach
2.1.
Algorithm
2.2.
Program
2.3.
Input
2.4.
Output
2.5.
Time Complexity
2.6.
Space Complexity
3.
Key Takeaways
Last Updated: Mar 27, 2024

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

Ujjawal Gupta
0 upvote

## 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.

NoteIf 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]);
}
}

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

3
3 5 2
23 11 45

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.

## Key Takeaways

In this blog, we have discussed the problem minimum decrements to make an array at most 0 such that all array elements are cyclically decremented after a number is reduced to 0. We have seen the greedy approach whose time complexity is O(N).

Check out the following problems -

If you want to explore more such types of problems then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Live masterclass