Minimum increments to make the array non-decreasing
Given an array A[] of size N along with an integer M such that 0 <= A[i] < M, the task is to output minimum number of operations required to sort A[] to non-decreasing order using following operation, choose an element let say A[i] and update it as (A[i] + 1) mod M.
Examples:
Input: N = 4, M = 5, A[] ={4, 1, 3, 2}
Output: 2
Explanation: The operations are performed as:
- Choose element A[0] = 4 and then update it as (A[0] + 1) mod 5 = (4 + 1) mod 5 = 0. Updated A[] = {0, 1, 3, 2}
- Choose element A[4] = 2 and then update it as (A[4] + 1) mod 5 = (2 + 1) mod 5 = 0. Updated A[] = {0, 1, 3, 3}
Now, it is visible that A[] is in non-decreasing order. Therefore, minimum number of operations required are 2.
Input: N = 5, M = 10, A = {0, 0, 1, 3, 7}
Output: 0
Explanation: A[] is already in non-decreasing order. Therefore, 0 operations are required.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Dynamic Programming as at every index we have 2 choices to either apply the operation or don’t apply the operation. We can make a check by using previous value, if the current value is greater than the previous value, then we can explore both the cases of applying and not applying the operation. Else if the current value is less than the previous value, then we have to apply the operation. After exploring all the cases, choose the minimum of them.
Step-by-step algorithm:
- Create a 2D array, say DP[][], with all elements initialize to -1.
- Define a recursive function, Rec(curr_ele, Prev, A, M) to explore both the cases when we apply the operation and increment the current value and also when we don’t apply the operation.
- Declare a variable let say minOperations to store the minimum number of operations.
- Explore the first case when we apply the operation on the current index: (Prev – A[curr_index] + M) % M + Rec(curr_index + 1, Prev, A, M)
- Explore the second case when we don’t apply the operation: Rec(curr_index + 1, A[curr_index], A, M
- Store the min of both the cases in minOperations.
- Return DP[curr_index][Prev] as minOperations.
Below is the implementation of the algorithm:
C++
// C++ code to implement the approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Intialising DP array int DP[1000][1000]; // Recursive Function to find minimum operations int Rec( int i, int prev, vector< int >& A, int M) { // If we reach at the end of array if (i == A.size()) return 0; // If we have cover up already this value if (DP[i][prev] != -1) return DP[i][prev]; // Taking the difference as steps int minOperations = (prev - A[i] + M) % M + Rec(i + 1, prev, A, M); // Check if prev number is smaller or equal if (A[i] >= prev) minOperations = min(Rec(i + 1, A[i], A, M), minOperations); // Return and update steps return DP[i][prev] = minOperations; } // Fuction to initialize DP array and iterate on it int minOperations( int N, int M, vector< int >& A) { // Fill all the values with -1 memset (DP, -1, sizeof (DP)); // Call Iterator function return Rec(0, 0, A, M); } // Driver code int main() { // Inputs int N = 3; int M = 2; vector< int > A = { 4, 3, 2 }; // Function call cout << minOperations(N, M, A); return 0; } |
Java
// Java program for the above approach import java.util.Arrays; import java.util.Vector; public class GFG { // Intialising DP array static int [][] DP = new int [ 1000 ][ 1000 ]; // Recursive Function to find minimum operations static int Rec( int i, int prev, Vector<Integer> A, int M) { // If we reach at the end of array if (i == A.size()) return 0 ; // If we have cover up already this value if (DP[i][prev] != - 1 ) return DP[i][prev]; // Taking the difference as steps int minOperations = (prev - A.get(i) + M) % M + Rec(i + 1 , prev, A, M); // Check if prev number is smaller or equal if (A.get(i) >= prev) minOperations = Math.min( Rec(i + 1 , A.get(i), A, M), minOperations); // Return and update steps return DP[i][prev] = minOperations; } // Function to initialize DP array and iterate on it static int minOperations( int N, int M, Vector<Integer> A) { // Fill all the values with -1 for ( int [] row : DP) Arrays.fill(row, - 1 ); // Call Iterator function return Rec( 0 , 0 , A, M); } // Driver code public static void main(String[] args) { // Inputs int N = 3 ; int M = 2 ; Vector<Integer> A = new Vector<>(Arrays.asList( 4 , 3 , 2 )); // Function call System.out.println(minOperations(N, M, A)); } } // This code is contributed by Susobhan Akhuli |
C#
using System; class Program { // Initializing DP array static int [,] DP = new int [1000, 1000]; // Recursive Function to find minimum operations static int Rec( int i, int prev, int [] A, int M) { // If we reach at the end of array if (i == A.Length) return 0; // If we have covered this value already if (DP[i, prev] != -1) return DP[i, prev]; // Taking the difference as steps int minOperations = (prev - A[i] + M) % M + Rec(i + 1, prev, A, M); // Check if prev number is smaller or equal if (A[i] >= prev) minOperations = Math.Min(Rec(i + 1, A[i], A, M), minOperations); // Return and update steps return DP[i, prev] = minOperations; } // Function to initialize DP array and iterate on it static int MinOperations( int N, int M, int [] A) { // Fill all the values with -1 for ( int i = 0; i < 1000; i++) { for ( int j = 0; j < 1000; j++) { DP[i, j] = -1; } } // Call Iterator function return Rec(0, 0, A, M); } // Driver code static void Main() { // Inputs int N = 3; int M = 2; int [] A = { 4, 3, 2 }; // Function call Console.WriteLine(MinOperations(N, M, A)); } } // This code is contributed by rambabuguphka |
Javascript
// Javascript program for the above approach // Recursive Function to find minimum operations function rec(i, prev, A, M, DP) { // If we reach at the end of array if (i === A.length) return 0; // If we have covered this value already if (DP[i][prev] !== -1) return DP[i][prev]; // Taking the difference as steps let minOperations = (prev - A[i] + M) % M + rec(i + 1, prev, A, M, DP); // Check if previous number is smaller or equal if (A[i] >= prev) minOperations = Math.min( rec(i + 1, A[i], A, M, DP), minOperations); // Return and update steps DP[i][prev] = minOperations; return DP[i][prev]; } // Function to initialize DP array and iterate on it function minOperations(N, M, A) { // Intialising DP array let DP = Array.from({ length: 1000 }, () => Array(1000).fill(-1)); // Call Iterator function return rec(0, 0, A, M, DP); } // Driver code ( function main() { // Inputs let N = 3; let M = 2; let A = [4, 3, 2]; // Function call console.log(minOperations(N, M, A)); })(); // This code is contributed by Susobhan Akhuli |
Python3
# Recursive function to find minimum operations def rec(i, prev, A, M, DP): # If we reach at the end of array if i = = len (A): return 0 # If we have covered this value already if DP[i][prev] ! = - 1 : return DP[i][prev] # Taking the difference as steps min_operations = (prev - A[i] + M) % M + rec(i + 1 , prev, A, M, DP) # Check if previous number is smaller or equal if A[i] > = prev: min_operations = min (rec(i + 1 , A[i], A, M, DP), min_operations) # Return and update steps DP[i][prev] = min_operations return DP[i][prev] # Function to initialize DP array and iterate on it def minOperations(N, M, A): # Intialising DP array with -1 DP = [[ - 1 ] * 1000 for _ in range ( 1000 )] # Call Iterator function return rec( 0 , 0 , A, M, DP) # Driver code if __name__ = = "__main__" : # Inputs N = 3 M = 2 A = [ 4 , 3 , 2 ] # Function call print (minOperations(N, M, A)) |
-1
Time Complexity: O(N*N), where N is the size of input array A[].
Auxiliary Space: O(N*N)