Given an array arr[] of n integers. Modify the array such that every element is at least as large as the previous element. This can be done by increasing the value of any element by 1. The task is to find the minimum number of moves required to make the array non-decreasing.
Examples:
Input: n = 5, arr[] = {8, 9, 2, 7, 7}
Output: 11
Explanation: The array should be modified to 8 9 9 9 9, this can be done by 11 moves(7 + 2 + 2).Input: n = 10, arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 0
Explanation: The array is already non decreasing.
Approach: The idea is to traverse the array and at any point when the current element is smaller than the previous one, then make the current one as the previous one and increase the count. Follow the steps below to solve the problem:
- Initialize the variable count as 0 to store the result.
- Iterate over the range [0, n) using the variable i and perform the following tasks:
- If arr[i] is less than arr[i-1] then set the value of arr[i] as arr[i-1] and increase the value of count by arr[i]-arr[i-1].
- After performing the above steps, print the value of count as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// value of countlong long countMoves(long int arr[], int n){ // Variable to store the answer long int count = 0; // Traverse the array for (int i = 0; i < n; i++) { if (i > 0) { // Make the changes if (arr[i] < arr[i - 1]) { count += (arr[i - 1] - arr[i]); arr[i] = arr[i - 1]; } } } // Return the answer return count;}// Driver Codeint main(){ int n = 5; long int arr[] = { 8, 9, 2, 7, 7 }; cout << countMoves(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the minimum // value of count static long countMoves(int arr[], int n) { // Variable to store the answer int count = 0; // Traverse the array for (int i = 0; i < n; i++) { if (i > 0) { // Make the changes if (arr[i] < arr[i - 1]) { count += (arr[i - 1] - arr[i]); arr[i] = arr[i - 1]; } } } // Return the answer return count; } // Driver Code public static void main(String[] args) { int n = 5; int arr[] = { 8, 9, 2, 7, 7 }; System.out.print(countMoves(arr, n)); }}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach# Function to find the minimum# value of countdef countMoves(arr, n): # Variable to store the answer count = 0 # Traverse the array for i in range(n): if (i > 0): # Make the changes if (arr[i] < arr[i - 1]): count += (arr[i - 1] - arr[i]) arr[i] = arr[i - 1] # Return the answer return count# Driver Coden = 5arr = [8, 9, 2, 7, 7]print(countMoves(arr, n))# This code is contributed by gfgking |
C#
// C# code to implement above approachusing System;class GFG{ // Function to find the minimum // value of count static long countMoves(int []arr, int n) { // Variable to store the answer int count = 0; // Traverse the array for (int i = 0; i < n; i++) { if (i > 0) { // Make the changes if (arr[i] < arr[i - 1]) { count += (arr[i - 1] - arr[i]); arr[i] = arr[i - 1]; } } } // Return the answer return count; } // Driver code public static void Main() { int n = 5; int []arr = { 8, 9, 2, 7, 7 }; Console.Write(countMoves(arr, n)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the minimum // value of count function countMoves(arr, n) { // Variable to store the answer let count = 0; // Traverse the array for (let i = 0; i < n; i++) { if (i > 0) { // Make the changes if (arr[i] < arr[i - 1]) { count += (arr[i - 1] - arr[i]); arr[i] = arr[i - 1]; } } } // Return the answer return count; } // Driver Code let n = 5; let arr = [8, 9, 2, 7, 7]; document.write(countMoves(arr, n)); // This code is contributed by Potta Lokesh </script> |
11
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
