Minimize subarray increments/decrements required to reduce all array elements to 0
Given an array arr[], select any subarray and apply any one of the below operations on each element of the subarray:
- Increment by one
- Decrement by one
The task is to print the minimum number of above-mentioned increment/decrement operations required to reduce all array elements to 0.
Examples:
Input: arr[] = {1, 3, 4, 1}
Output: 4
Explanation:
Optimal steps to reduce all array elements to 0 are as follows:
Step 1: Select subarray [1, 3, 4, 1] and convert it to [0, 2, 3, 0], by decrementing each element by 1
Array modifies to {0, 2, 3, 0}
Step 2: Select subarray [2, 3] and convert it to [1, 2], by decrementing each element by 1
Array modifies to {0, 1, 2, 0}
Step 3: Select subarray [1, 2] and convert it to [0, 1], by decrementing each element by 1
Array modifies to {0, 0, 1, 0}
Step 4: Select subarray [1] convert it to [0]
Array modifies to {0, 0, 0, 0}
Therefore, minimum number of steps required is 4.Input: arr[] = {-2, 0, -3, 1, 2}
Output: 5
Explanation:
Optimal steps to reduce all array elements to 0 are as follows:
Step 1: Select subarray [-2, 0, -3] and convert it to [-1, 0, -2], by incrementing each element by 1 except 0.
Array modifies to {-1, 0, -2, 1, 2}
Step 2: Select subarray [-1, 0, -2] and convert it to [0, 0, -1], by incrementing each element by 1 except 0.
Array modifies to {0, 0, -1, 1, 2}
Step 3: Select subarray [-1] convert it to [0]
Array modifies to {0, 0, 0, 1, 2}
Step 4: Select subarray [1, 2] and convert it to [0, 1], by decrementing each element by 1
Array modifies to {0, 0, 0, 0, 1}
Step 5: Select [1] convert it to [0]
Array modifies to {0, 0, 0, 0, 0}
Therefore, minimum number of steps required is 5
Approach: To solve the problem, traverse the array and find the minimum negative number and the maximum positive number. The sum of their absolute values is the minimum number of operations required.
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 count the minimum // number of operations required int minOperation( int arr[], int N) { int minOp = INT_MIN; int minNeg = 0, maxPos = 0; // Traverse the array for ( int i = 0; i < N; i++) { // If array element // is negative if (arr[i] < 0) { if (arr[i] < minNeg) // Update minimum negative minNeg = arr[i]; } else { if (arr[i] > maxPos) // Update maximum positive maxPos = arr[i]; } } // Return minOp return abs (minNeg) + maxPos; } // Driver Code int main() { int arr[] = {1, 3, 4, 1}; int N = sizeof (arr) / sizeof (arr[0]); cout << minOperation(arr, N); } //This code is contributed by Rajput-Ji |
Java
// Java program of the // above approach import java.util.*; import java.lang.*; class GFG { // Function to count the minimum // number of operations required static int minOperation( int [] arr) { int minOp = Integer.MIN_VALUE; int minNeg = 0 , maxPos = 0 ; // Traverse the array for ( int i = 0 ; i < arr.length; i++) { // If array element // is negative if (arr[i] < 0 ) { if (arr[i] < minNeg) // Update minimum negative minNeg = arr[i]; } else { if (arr[i] > maxPos) // Update maximum positive maxPos = arr[i]; } } // Return minOp return Math.abs(minNeg) + maxPos; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 3 , 4 , 1 }; System.out.println(minOperation(arr)); } } |
Python3
# Python3 program of the # above approach import sys # Function to count the minimum # number of operations required def minOperation(arr): minOp = sys.maxsize minNeg = 0 maxPos = 0 # Traverse the array for i in range ( len (arr)): # If array element # is negative if (arr[i] < 0 ): if (arr[i] < minNeg): # Update minimum negative minNeg = arr[i] else : if arr[i] > maxPos: # Update maximum position maxPos = arr[i] # Return minOp return abs (minNeg) + maxPos # Driver code if __name__ = = "__main__" : arr = [ 1 , 3 , 4 , 1 ] print (minOperation(arr)) # This code is contributed by Rutvik_56 |
C#
// C# program of the // above approach using System; class GFG{ // Function to count the minimum // number of operations required static int minOperation( int [] arr) { int minOp = int .MinValue; int minNeg = 0, maxPos = 0; // Traverse the array for ( int i = 0; i < arr.Length; i++) { // If array element // is negative if (arr[i] < 0) { if (arr[i] < minNeg) // Update minimum negative minNeg = arr[i]; } else { if (arr[i] > maxPos) // Update maximum positive maxPos = arr[i]; } } // Return minOp return Math.Abs(minNeg) + maxPos; } // Driver Code public static void Main(String[] args) { int []arr = {1, 3, 4, 1}; Console.WriteLine(minOperation(arr)); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to implement // the above approach // Function to count the minimum // number of operations required function minOperation(arr) { let minOp = Number.MIN_VALUE; let minNeg = 0, maxPos = 0; // Traverse the array for (let i = 0; i < arr.length; i++) { // If array element // is negative if (arr[i] < 0) { if (arr[i] < minNeg) // Update minimum negative minNeg = arr[i]; } else { if (arr[i] > maxPos) // Update maximum positive maxPos = arr[i]; } } // Return minOp return Math.abs(minNeg) + maxPos; } // Driver code let arr = [ 1, 3, 4, 1 ]; document.write(minOperation(arr)); // This code is contributed by target_2. </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)