Given an array arr[] consisting of N integers, the task is to find the minimum number of operations, which involves incrementing all elements of a subarray by 1, required to make the array non-increasing.
Examples:
Input: arr[] = {1, 3, 4, 1, 2}
Output: 4
Explanation:
In operation 1: Choose the subarray {1} and increase its value by 1. Now arr[] = {2, 3, 4, 1, 2}
In operation 2: Choose the subarray {2} and increase its value by 1. Now arr[] = {3, 3, 4, 1, 2}
In operation 3: Choose the subarray {3, 3} and increase its value by 1. Now arr[] = {4, 4, 4, 1, 2}
In operation 4: Choose the subarray {1} and increase its value by 1. Now arr[] = {4, 4, 4, 2, 2}
Thus, it took 4 operations to make the array non-increasing.Input: arr[] = {10, 9, 8, 7, 7}
Output: 0
Explanation:
The array is already non-increasing
Approach: The approach is based on the fact that the operations can only be performed on subarrays. So only check for contiguous elements. Below are the steps:
- Otherwise, initialize a variable, say res, to store the count of operations required.
- Now, traverse the array and for each element, check if the element at index i is smaller than the element at index (i + 1). If found to be true, then add the difference between them to res, since both the elements need to be made equal to make the array non-increasing.
- Otherwise, move to the next element and repeat the above steps.
- Finally, after complete the traversal of the array, print the final value of res.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// number of operations required to// make the array non-increasingint getMinOps(int arr[], int n){ // Stores the count of // required operations int res = 0; for (int i = 0; i < n - 1; i++) { // If arr[i] > arr[i+1], // no increments required. // Otherwise, add their // difference to the answer res += max(arr[i + 1] - arr[i], 0); } // Return the result res return res;}// Driver Codeint main(){ int arr[] = {1, 3, 4, 1, 2}; int N = sizeof(arr) / sizeof(arr[0]); cout << getMinOps(arr, N);}// This code is contributed by shikhasingrajput |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum // number of operations required to // make the array non-increasing public static int getMinOps(int[] arr) { // Stores the count of // required operations int res = 0; for (int i = 0; i < arr.length - 1; i++) { // If arr[i] > arr[i+1], // no increments required. // Otherwise, add their // difference to the answer res += Math.max(arr[i + 1] - arr[i], 0); } // Return the result res return res; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 3, 4, 1, 2 }; System.out.println(getMinOps(arr)); }} |
Python3
# Python3 Program to implement# the above approach# Function to find the minimum# number of operations required to# make the array non-increasingdef getMinOps(arr): # Stores the count of # required operations res = 0 for i in range(len(arr) - 1): # If arr[i] > arr[i+1], # no increments required. # Otherwise, add their # difference to the answer res += max(arr[i + 1] - arr[i], 0) # Return the result res return res# Driver Code# Given arrayarr = [ 1, 3, 4, 1, 2 ]# Function callprint(getMinOps(arr))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum// number of operations required to// make the array non-increasingpublic static int getMinOps(int[] arr){ // Stores the count of // required operations int res = 0; for(int i = 0; i < arr.Length - 1; i++) { // If arr[i] > arr[i+1], // no increments required. // Otherwise, add their // difference to the answer res += Math.Max(arr[i + 1] - arr[i], 0); } // Return the result res return res;}// Driver Codepublic static void Main(String[] args){ int[] arr = { 1, 3, 4, 1, 2 }; Console.WriteLine(getMinOps(arr));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach // Function to find the minimum // number of operations required to // make the array non-increasing function getMinOps(arr) { // Stores the count of // required operations var res = 0; for (i = 0; i < arr.length - 1; i++) { // If arr[i] > arr[i+1], // no increments required. // Otherwise, add their // difference to the answer res += Math.max(arr[i + 1] - arr[i], 0); } // Return the result res return res; } // Driver Code var arr = [ 1, 3, 4, 1, 2 ]; document.write(getMinOps(arr));// This code contributed by umadevi9616</script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
