Given an array arr[] of size N. The task is to make all the array elements equal to zero by applying the minimum number of operations.
Following operations are allowed:
- Select an index i and decrease each element by 1 for the prefix up to that index.
- Select an index i and decrease each element by 1 for the suffix starting from that index.
- Increase all the elements of the array by 1.
Examples:
Input: arr[] = {2, 4, 6, 3, 7}
Output: Minimum operations: 12
Explanation: Select Index 0, and decrease all the elements from
index 1 to 4 by 2 in 2 operations, new arr[] would be {2, 2, 4, 1, 5}.
Select Index 1, and decrease all the elements from index 2 to 4
by 2 in 2 operations, new arr[] would be {2, 2, 2, -1, 3}
Select Index 3, and decrease all the elements from index 0 to 2
by 3 in 3 operations, new arr[] would be {-1, -1, -1, -1, 3}
Select Index 3, and decrease element of index 4 by 4 in 4 operations,
New arr[] would be {-1, -1, -1, -1, -1}
Increase all the elements by 1 in 1 operation,
Final arr[] would be {0, 0, 0, 0, 0}
Total, operations would be 2 + 2 + 3 + 4 + 1 = 12Input: arr[] = {1, 3, 5, 7, 5, 2, 8}
Output: Minimum operations: 21
Approach:
The following problem can be solved using Greedy Approach.
Initially make all elements equal to the first element and then decrement them to have value as 0.
To do this following steps can be taken:
- For making all the elements equal to the first element, we will use the difference between the consecutive elements. ( arr[i+1] – arr[i] ).
- If the difference (diff = arr[i+1] – arr[i]) is positive, decrease the elements of suffix starting from index (i+1).
- Number of operations required = abs( diff )
- If the difference (diff = arr[i+1] – arr[i]) is negative, decrease the elements of prefix up to index i.
- Number of operations required = abs( diff ) . Decreasing the prefix will also decrease the first element of the array by abs( diff).
- Finally, the total number of required operations will be operations calculated through the absolute difference between the consecutive elements of the array plus the absolute value of the first element of the array.
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number of// operations required to make all// array elements zeroint minimumOperations(int arr[], int n){ int i; // It will count total no. of operations int operations = 0; for (int i = 0; i < n - 1; i++) { // Calculate the difference and // add its absolute value to // the no. of operations operations += abs(arr[i + 1] - arr[i]); // If the changes are done in prefix // then update first element of array if (arr[i + 1] - arr[i] < 0) { arr[0] -= (abs(arr[i + 1] - arr[i])); } } // Now all the elements of the array are // equal to arr[0], add absolute value // of arr[0] to the no. of operations operations += abs(arr[0]); // Return the total number of operations return operations;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 3, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << "Minimum operations: " << minimumOperations(arr, N); return 0;} |
Java
// Java program to of the above approachimport java.util.*;class GFG {// Function to find minimum number of// operations required to make all// array elements zerostatic int minimumOperations(int arr[], int n){ int i; // It will count total no. of operations int operations = 0; for (i = 0; i < n - 1; i++) { // Calculate the difference and // add its absolute value to // the no. of operations operations += Math.abs(arr[i + 1] - arr[i]); // If the changes are done in prefix // then update first element of array if (arr[i + 1] - arr[i] < 0) { arr[0] -= (Math.abs(arr[i + 1] - arr[i])); } } // Now all the elements of the array are // equal to arr[0], add absolute value // of arr[0] to the no. of operations operations += Math.abs(arr[0]); // Return the total number of operations return operations;}// Driver Codepublic static void main(String args[]){ int arr[] = { 2, 4, 6, 3, 7 }; int N = arr.length; // Function call System.out.print("Minimum operations: " + minimumOperations(arr, N));}}// This code is contributed by sanjoy_62. |
Python3
# Python code to implement the approach# Function to find minimum number of# operations required to make all# array elements zerodef minimumOperations(arr, n): i = 0 # It will count total no. of operations operations = 0 for i in range(n-1): # Calculate the difference and # add its absolute value to # the no. of operations operations += abs(arr[i + 1] - arr[i]) # If the changes are done in prefix # then update first element of array if (arr[i + 1] - arr[i]) < 0: arr[0] -= (abs(arr[i + 1] - arr[i])) # Now all the elements of the array are # equal to arr[0], add absolute value # of arr[0] to the no. of operations operations += abs(arr[0]) # Return the total number of operations return operations# Driver codeif __name__ == "__main__": arr = [2, 4, 6, 3, 7] N = 5 # Function call print("Minimum operations: ", minimumOperations(arr, N))# This code is contributed by Rohit Pradhan |
Javascript
<script>// Javascript code to implement the approach// Function to find minimum number of// operations required to make all// array elements zerofunction minimumOperations(arr,n){ let i; // It will count total no. of operations let operations = 0; for (let i = 0; i < n - 1; i++) { // Calculate the difference and // add its absolute value to // the no. of operations operations += Math.abs(arr[i + 1] - arr[i]); // If the changes are done in prefix // then update first element of array if (arr[i + 1] - arr[i] < 0) { arr[0] -= (Math.abs(arr[i + 1] - arr[i])); } } // Now all the elements of the array are // equal to arr[0], add absolute value // of arr[0] to the no. of operations operations += Math.abs(arr[0]); // Return the total number of operations return operations;}// Driver code let arr = [ 2, 4, 6, 3, 7 ]; let N = arr.length; // Function call document.write( "Minimum operations: " + minimumOperations(arr, N)); // This code is contributed by satwik4409. </script> |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG {// Function to find minimum number of// operations required to make all// array elements zerostatic int minimumOperations(int[] arr, int n){ int i; // It will count total no. of operations int operations = 0; for (i = 0; i < n - 1; i++) { // Calculate the difference and // add its absolute value to // the no. of operations operations += Math.Abs(arr[i + 1] - arr[i]); // If the changes are done in prefix // then update first element of array if (arr[i + 1] - arr[i] < 0) { arr[0] -= (Math.Abs(arr[i + 1] - arr[i])); } } // Now all the elements of the array are // equal to arr[0], add absolute value // of arr[0] to the no. of operations operations += Math.Abs(arr[0]); // Return the total number of operations return operations;} // Driver Codepublic static void Main(string[] args){ int[] arr = { 2, 4, 6, 3, 7 }; int N = arr.Length; // Function call Console.WriteLine("Minimum operations: " + minimumOperations(arr, N));}} |
Output
Minimum operations: 12
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
