Given an array arr[] of N integers, the task is to sort the array in non-decreasing order by performing the minimum number of operations. In a single operation, an element of the array can either be incremented or decremented by 1. Print the minimum number of operations required.
Examples:
Input: arr[] = {1, 2, 1, 4, 3}
Output: 2
Add 1 to the 3rd element(1) and subtract 1 from
the 4th element(4) to get {1, 2, 2, 3, 3}
Input: arr[] = {1, 2, 2, 100}
Output: 0
Given array is already sorted.
Observation: Since we would like to minimize the number of operations needed to sort the array the following should hold:
- A number will never be decreased to value lesser than the minimum of the initial array.
- A number will never be increased to a value greater than the maximum of the initial array.
- The number of operations required to change a number from X to Y is abs(X – Y).
Approach : Based on the above observation, this problem can be solved using dynamic programming.
- Let DP(i, j) represent the minimum operations needed to make the 1st i elements of the array sorted in non-decreasing order when the ith element is equal to j.
- Now DP(N, j) needs to be calculated for all possible values of j where N is the size of the array. According to the observations, j ? smallest element of the initial array and j ? the largest element of the initial array.
- The base cases in the DP(i, j) where i = 1 can be easily answered. What are the minimum operations needs to sort the 1st element in non-decreasing order such that the 1st element is equal to j?. DP(1, j) = abs( array[1] – j).
- Now consider DP(i, j) for i > 1. If ith element is set to j then the 1st i – 1 elements need to be sorted and the (i – 1)th element has to be ? j i.e. DP(i, j) = (minimum of DP(i – 1, k) where k goes from 1 to j) + abs(array[i] – j)
- Using the above recurrence relation and the base cases, the result can be easily calculated.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// of given operations required// to sort the arrayint getMinimumOps(vector<int> ar){ // Number of elements in the array int n = ar.size(); // Smallest element in the array int small = *min_element(ar.begin(), ar.end()); // Largest element in the array int large = *max_element(ar.begin(), ar.end()); /* dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j */ int dp[n][large + 1]; // Fill the dp[]][ array for base cases for (int j = small; j <= large; j++) { dp[0][j] = abs(ar[0] - j); } /* Using results for the first (i - 1) elements, calculate the result for the ith element */ for (int i = 1; i < n; i++) { int minimum = INT_MAX; for (int j = small; j <= large; j++) { /* If the ith element is j then we can have any value from small to j for the i-1 th element We choose the one that requires the minimum operations */ minimum = min(minimum, dp[i - 1][j]); dp[i][j] = minimum + abs(ar[i] - j); } } /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ int ans = INT_MAX; for (int j = small; j <= large; j++) { ans = min(ans, dp[n - 1][j]); } return ans;}// Driver codeint main(){ vector<int> ar = { 1, 2, 1, 4, 3 }; cout << getMinimumOps(ar); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function to return the minimum number// of given operations required// to sort the arraystatic int getMinimumOps(Vector<Integer> ar){ // Number of elements in the array int n = ar.size(); // Smallest element in the array int small = Collections.min(ar); // Largest element in the array int large = Collections.max(ar); /* dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j */ int [][]dp = new int[n][large + 1]; // Fill the dp[]][ array for base cases for (int j = small; j <= large; j++) { dp[0][j] = Math.abs(ar.get(0) - j); } /* Using results for the first (i - 1) elements, calculate the result for the ith element */ for (int i = 1; i < n; i++) { int minimum = Integer.MAX_VALUE; for (int j = small; j <= large; j++) { /* If the ith element is j then we can have any value from small to j for the i-1 th element We choose the one that requires the minimum operations */ minimum = Math.min(minimum, dp[i - 1][j]); dp[i][j] = minimum + Math.abs(ar.get(i) - j); } } /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ int ans = Integer.MAX_VALUE; for (int j = small; j <= large; j++) { ans = Math.min(ans, dp[n - 1][j]); } return ans;}// Driver codepublic static void main(String[] args){ Integer []arr = { 1, 2, 1, 4, 3 }; Vector<Integer> ar = new Vector<>(Arrays.asList(arr)); System.out.println(getMinimumOps(ar));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the minimum number# of given operations required# to sort the arraydef getMinimumOps(ar): # Number of elements in the array n = len(ar) # Smallest element in the array small = min(ar) # Largest element in the array large = max(ar) """ dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j """ dp = [[ 0 for i in range(large + 1)] for i in range(n)] # Fill the dp[]][ array for base cases for j in range(small, large + 1): dp[0][j] = abs(ar[0] - j) """ /* Using results for the first (i - 1) elements, calculate the result for the ith element */ """ for i in range(1, n): minimum = 10**9 for j in range(small, large + 1): # """ # /* # If the ith element is j then we can have # any value from small to j for the i-1 th # element # We choose the one that requires the # minimum operations # """ minimum = min(minimum, dp[i - 1][j]) dp[i][j] = minimum + abs(ar[i] - j) """ /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ """ ans = 10**9 for j in range(small, large + 1): ans = min(ans, dp[n - 1][j]) return ans# Driver codear = [1, 2, 1, 4, 3]print(getMinimumOps(ar))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Linq;using System.Collections.Generic; class GFG {// Function to return the minimum number// of given operations required// to sort the arraystatic int getMinimumOps(List<int> ar){ // Number of elements in the array int n = ar.Count; // Smallest element in the array int small = ar.Min(); // Largest element in the array int large = ar.Max(); /* dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j */ int [,]dp = new int[n, large + 1]; // Fill the dp[], array for base cases for (int j = small; j <= large; j++) { dp[0, j] = Math.Abs(ar[0] - j); } /* Using results for the first (i - 1) elements, calculate the result for the ith element */ for (int i = 1; i < n; i++) { int minimum = int.MaxValue; for (int j = small; j <= large; j++) { /* If the ith element is j then we can have any value from small to j for the i-1 th element We choose the one that requires the minimum operations */ minimum = Math.Min(minimum, dp[i - 1, j]); dp[i, j] = minimum + Math.Abs(ar[i] - j); } } /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ int ans = int.MaxValue; for (int j = small; j <= large; j++) { ans = Math.Min(ans, dp[n - 1, j]); } return ans;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 2, 1, 4, 3 }; List<int> ar = new List<int>(arr); Console.WriteLine(getMinimumOps(ar));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the minimum number// of given operations required// to sort the arrayfunction getMinimumOps(ar){ // Number of elements in the array var n = ar.length; // Smallest element in the array var small = Math.min.apply(Math,ar); // Largest element in the array var large = Math.max.apply(Math,ar); /* dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j */ var dp = new Array(n); var i,j; for(i=0;i<dp.length;i++) dp[i] = new Array(large+1); // Fill the dp[]][ array for base cases for (j = small; j <= large; j++) { dp[0][j] = Math.abs(ar[0] - j); } /* Using results for the first (i - 1) elements, calculate the result for the ith element */ for (i = 1; i < n; i++) { var minimum = 2147483647; for (j = small; j <= large; j++) { /* If the ith element is j then we can have any value from small to j for the i-1 th element We choose the one that requires the minimum operations */ minimum = Math.min(minimum, dp[i - 1][j]); dp[i][j] = minimum + Math.abs(ar[i] - j); } } /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ var ans = 2147483647; for (j = small; j <= large; j++) { ans = Math.min(ans, dp[n - 1][j]); } return ans;}// Driver code var ar = [1, 2, 1, 4, 3]; document.write(getMinimumOps(ar));</script> |
Output
2
Complexity Analysis:
Time Complexity: O(N*R), Time complexity for the above approach is O(N * R) where N is the number of elements in the array and R = largest – smallest element of the array + 1.
Auxiliary Space: O(N * large)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size large+1.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a 1d vector curr used to store the current values from previous computations.
- After every iteration assign the value of curr to dp for further iteration.
- Initialize a variable ans to store the final answer and update it by iterating through the Dp.
- At last return and print the final answer stored in ans .
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// of given operations required// to sort the arrayint getMinimumOps(vector<int> ar){ // Number of elements in the array int n = ar.size(); // Smallest element in the array int small = *min_element(ar.begin(), ar.end()); // Largest element in the array int large = *max_element(ar.begin(), ar.end()); // create vector to store value of subproblems vector<int> dp(large + 1); // initialize base case for (int j = small; j <= large; j++) { dp[j] = abs(ar[0] - j); } // iterate iver subproblems to get the current // value from previous computations for (int i = 1; i < n; i++) { int minimum = INT_MAX; // create vector to store current row values vector<int> curr(large + 1); for (int j = small; j <= large; j++) { minimum = min(minimum, dp[j]); curr[j] = minimum + abs(ar[i] - j); } // assigning values for further iterations dp = curr; } // to store answer int ans = INT_MAX; for (int j = small; j <= large; j++) { // update answer ans = min(ans, dp[j]); } // return final answer return ans;}// Driver codeint main(){ vector<int> ar = { 1, 2, 1, 4, 3 }; // function call cout << getMinimumOps(ar); return 0;} |
Java
import java.util.*;public class Main { // Function to return the minimum number of given // operations required to sort the array public static int getMinimumOps(List<Integer> ar) { // Number of elements in the array int n = ar.size(); // Smallest element in the array int small = Collections.min(ar); // Largest element in the array int large = Collections.max(ar); // create array to store value of subproblems int[] dp = new int[large + 1]; // initialize base case for (int j = small; j <= large; j++) { dp[j] = Math.abs(ar.get(0) - j); } // iterate over subproblems to get the current value from previous computations for (int i = 1; i < n; i++) { int minimum = Integer.MAX_VALUE; // create array to store current row values int[] curr = new int[large + 1]; for (int j = small; j <= large; j++) { minimum = Math.min(minimum, dp[j]); curr[j] = minimum + Math.abs(ar.get(i) - j); } // assigning values for further iterations dp = curr; } // to store answer int ans = Integer.MAX_VALUE; for (int j = small; j <= large; j++) { // update answer ans = Math.min(ans, dp[j]); } // return final answer return ans; } // Driver code public static void main(String[] args) { List<Integer> ar = Arrays.asList(1, 2, 1, 4, 3); // function call System.out.println(getMinimumOps(ar)); }} |
Python3
# Function to return the minimum number of operations required to sort the arraydef getMinimumOps(ar): # Number of elements in the array n = len(ar) # Smallest element in the array small = min(ar) # Largest element in the array large = max(ar) # create list to store value of subproblems dp = [0] * (large + 1) # initialize base case for j in range(small, large + 1): dp[j] = abs(ar[0] - j) # iterate over subproblems to get the current value # from previous computations for i in range(1, n): minimum = float('inf') # create list to store current row values curr = [0] * (large + 1) for j in range(small, large + 1): minimum = min(minimum, dp[j]) curr[j] = minimum + abs(ar[i] - j) # assigning values for further iterations dp = curr # to store answer ans = float('inf') for j in range(small, large + 1): # update answer ans = min(ans, dp[j]) # return final answer return ans# Driver codear = [1, 2, 1, 4, 3]# function callprint(getMinimumOps(ar)) |
C#
using System;using System.Collections.Generic;using System.Linq;class MainClass { // Function to return the minimum number // of given operations required to sort array public static int GetMinimumOps(List<int> ar) { // Number of elements in the array int n = ar.Count; // Smallest element in the array int small = ar.Min(); // Largest element in the array int large = ar.Max(); // create array to store value of subproblems int[] dp = new int[large + 1]; // initialize base case for (int j = small; j <= large; j++) { dp[j] = Math.Abs(ar[0] - j); } // iterate over subproblems to get the // current value from previous computations for (int i = 1; i < n; i++) { int minimum = Int32.MaxValue; // create array to store current row values int[] curr = new int[large + 1]; for (int j = small; j <= large; j++) { minimum = Math.Min(minimum, dp[j]); curr[j] = minimum + Math.Abs(ar[i] - j); } // assigning values for further iterations dp = curr; } // to store answer int ans = Int32.MaxValue; for (int j = small; j <= large; j++) { // update answer ans = Math.Min(ans, dp[j]); } // return final answer return ans; } // Driver Code public static void Main() { List<int> ar = new List<int>() { 1, 2, 1, 4, 3 }; // function call Console.WriteLine(GetMinimumOps(ar)); }} |
Javascript
function getMinimumOps(ar) { // Number of elements in the array let n = ar.length; // Smallest element in the array let small = Math.min(...ar); // Largest element in the array let large = Math.max(...ar); // create array to store value of subproblems let dp = new Array(large + 1); // initialize base case for (let j = small; j <= large; j++) { dp[j] = Math.abs(ar[0] - j); } // iterate over subproblems to get the current // value from previous computations for (let i = 1; i < n; i++) { let minimum = Number.MAX_VALUE; // create array to store current row values let curr = new Array(large + 1); for (let j = small; j <= large; j++) { minimum = Math.min(minimum, dp[j]); curr[j] = minimum + Math.abs(ar[i] - j); } // assigning values for further iterations dp = curr; } // to store answer let ans = Number.MAX_VALUE; for (let j = small; j <= large; j++) { // update answer ans = Math.min(ans, dp[j]); } // return final answer return ans;}// Driver codelet ar = [1, 2, 1, 4, 3]; // function callconsole.log(getMinimumOps(ar)); |
Output
2
Time Complexity: O(N*Large)
Auxiliary Space: O(Large)
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!
