Minimize replacements to sort an array with elements 1, 2, and 3
Given an array arr[] of length N containing elements 1, 2 and 3. The task is to find the minimum number of operations required to make array sorted by replacing any elements of given array with either 1, 2 or 3.
Examples:
Input: arr[] = {2, 1, 3, 2, 1}
Output: 3
Explanation:
- 1st Operation: Choose index i = 0, Update arr[0] = 2 into 1. Then updated arr[] = {1, 1, 3, 2, 1}
- 2nd Operation: Choose index i = 2, Update arr[2] = 3 into 2. Then updated arr[] = {1, 1, 2, 2, 1}
- 3rd Operation: Choose index i = 4, Update arr[4] = 1 into 2. Then updated arr[] = {1, 1, 2, 2, 2}
Now, it is clearly visible that arr[] is sorted and required operations were 3. Which is minimum possible.
Input: arr[] = {1, 3, 2, 1, 3, 3}
Output: 2
Explanation: It can be verified that arr[] can be sorted under 2 operations.
Approach: Implement the idea below to solve the problem
As we have choice to update any arr[i] into either 1, 2 or 3. Then, Dynamic Programming can be used to solve this problem. The main concept of DP in the problem will be:
DP[i][j] will store the minimum number of operations to make first i elements of array sorted by making current element j(1, 2 or 3)
Transition:
- DP[i][1] = DP[i β 1][1] + (arr[i β 1] != 1) (If ith element is made 1, then (i β 1)th element should be 1 as well).
- DP[i][2] = min(DP[i β 1][1], [i β 1][2]) + (arr[i β 1] != 2) (If the ith element is made 2 then (i β 1)th element should be either 1 or 2).
- DP[i][3] = min({DP[i β 1][1], DP[i β 1][2], DP[i β 1][3]}) + (arr[i β 1] != 3) (If the ith element is made 3 then (i β 1)th element should be either 1, 2 or 3).
Step-by-step approach:
- Declare a 2D array let say DP of size [N + 1][4] with all initialized to zero.
- Calculate answer for ith state by iterating from i = 1 to N and follow below-mentioned steps:
- In each iteration update DP table as
- DP[i][1] = DP[i β 1][1] + (arr[i β 1] != 1)
- DP[i][2] = min(DP[i β 1][1], DP[i β 1][2]) + (arr[i β 1] != 2)
- DP[i][3] = min({DP[i β 1][1], DP[i β 1][2], DP[i β 1][3]}) + (arr[i β 1] != 3)
- In each iteration update DP table as
- Return min(DP[N][1], DP[N][2], DP[N][3])
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to Minimum replacements to // make array sorted containing only numbers 1, 2 and 3 int minOperations( int arr[], int N) { // DP array initalized with 0 vector<vector< int > > dp(N + 1, vector< int >(4, 0)); // calculating answer till i'th element for ( int i = 1; i <= N; i++) { // i'th element is made 1 then (i - 1)th element // should be 1 dp[i][1] = dp[i - 1][1] + (arr[i - 1] != 1); // i'th element is made 2 then (i- 1)th element // should be either 1 or 2 dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + (arr[i - 1] != 2); // if the i'th element is made 3 then (i - 1)th // element should be either 1, 2 or 3 dp[i][3] = min({ dp[i - 1][1], dp[i - 1][2], dp[i - 1][3] }) + (arr[i - 1] != 3); } // returning final answer minimum number of operations // required to make array sorted by by replacing i'th // element by 1, 2 or 3 return min({ dp[N][1], dp[N][2], dp[N][3] }); } // Driver Code int main() { // Input int N = 5; int arr[] = { 2, 1, 3, 2, 1 }; // Function Call cout << minOperations(arr, N) << endl; return 0; } |
Java
public class MinOperations { public static int minOperations( int [] arr, int N) { // DP array initialized with 0 int [][] dp = new int [N + 1 ][ 4 ]; // Calculating answer till i'th element for ( int i = 1 ; i <= N; i++) { // i'th element is made 1 then (i - 1)th element // should be 1 dp[i][ 1 ] = dp[i - 1 ][ 1 ] + (arr[i - 1 ] != 1 ? 1 : 0 ); // i'th element is made 2 then (i- 1)th element // should be either 1 or 2 dp[i][ 2 ] = Math.min(dp[i - 1 ][ 1 ], dp[i - 1 ][ 2 ]) + (arr[i - 1 ] != 2 ? 1 : 0 ); // If the i'th element is made 3 then (i - 1)th // element should be either 1, 2, or 3 dp[i][ 3 ] = Math.min(Math.min(dp[i - 1 ][ 1 ], dp[i - 1 ][ 2 ]), dp[i - 1 ][ 3 ]) + (arr[i - 1 ] != 3 ? 1 : 0 ); } // Returning the final answer, the minimum number of operations // required to make the array sorted by replacing i'th // element by 1, 2, or 3 return Math.min(Math.min(dp[N][ 1 ], dp[N][ 2 ]), dp[N][ 3 ]); } // Driver Code public static void main(String[] args) { // Input int N = 5 ; int [] arr = { 2 , 1 , 3 , 2 , 1 }; // Function Call System.out.println(minOperations(arr, N)); } } |
Python3
# Function to Minimum replacements to # make array sorted containing only numbers 1, 2 and 3 def min_operations(arr, N): # DP array initialized with 0 dp = [[ 0 ] * 4 for _ in range (N + 1 )] # calculating answer till i'th element for i in range ( 1 , N + 1 ): # i'th element is made 1 then (i - 1)th element # should be 1 dp[i][ 1 ] = dp[i - 1 ][ 1 ] + (arr[i - 1 ] ! = 1 ) # i'th element is made 2 then (i- 1)th element # should be either 1 or 2 dp[i][ 2 ] = min (dp[i - 1 ][ 1 ], dp[i - 1 ][ 2 ]) + (arr[i - 1 ] ! = 2 ) # if the i'th element is made 3 then (i - 1)th # element should be either 1, 2, or 3 dp[i][ 3 ] = min (dp[i - 1 ][ 1 ], dp[i - 1 ][ 2 ], dp[i - 1 ][ 3 ]) + (arr[i - 1 ] ! = 3 ) # returning the final answer, the minimum number of operations # required to make the array sorted by replacing i'th # element by 1, 2, or 3 return min (dp[N][ 1 ], dp[N][ 2 ], dp[N][ 3 ]) # Driver Code if __name__ = = "__main__" : # Input N = 5 arr = [ 2 , 1 , 3 , 2 , 1 ] # Function Call print (min_operations(arr, N)) |
C#
using System; class GFG { // Function to Minimum replacements to // make array sorted containing only numbers 1, 2 and 3 static int MinOperations( int [] arr, int N) { // DP array initialized with 0 int [][] dp = new int [N + 1][]; for ( int i = 0; i <= N; i++) { dp[i] = new int [4]; } // calculating answer till i'th element for ( int i = 1; i <= N; i++) { // i'th element is made 1 then (i - 1)th element // should be 1 dp[i][1] = dp[i - 1][1] + (arr[i - 1] != 1 ? 1 : 0); // i'th element is made 2 then (i- 1)th element // should be either 1 or 2 dp[i][2] = Math.Min(dp[i - 1][1], dp[i - 1][2]) + (arr[i - 1] != 2 ? 1 : 0); // if the i'th element is made 3 then (i - 1)th // element should be either 1, 2 or 3 dp[i][3] = Math.Min(Math.Min(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][3]) + (arr[i - 1] != 3 ? 1 : 0); } // returning final answer minimum number of operations // required to make array sorted by replacing i'th // element by 1, 2 or 3 return Math.Min(Math.Min(dp[N][1], dp[N][2]), dp[N][3]); } // Driver Code static void Main() { // Input int N = 5; int [] arr = { 2, 1, 3, 2, 1 }; // Function Call Console.WriteLine(MinOperations(arr, N)); } } |
Javascript
// Function to find the minimum replacements required to make the array sorted containing only numbers 1, 2, and 3 function minOperations(arr) { const N = arr.length; // Initializing DP array with 0 const dp = new Array(N + 1).fill(0).map(() => new Array(4).fill(0)); // Calculating answer till ith element for (let i = 1; i <= N; i++) { // If ith element is made 1, then (i - 1)th element should be 1 dp[i][1] = dp[i - 1][1] + (arr[i - 1] !== 1 ? 1 : 0); // If ith element is made 2, then (i - 1)th element should be either 1 or 2 dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2]) + (arr[i - 1] !== 2 ? 1 : 0); // If ith element is made 3, then (i - 1)th element should be either 1, 2, or 3 dp[i][3] = Math.min(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + (arr[i - 1] !== 3 ? 1 : 0); } // Returning the final answer: minimum number of operations required to make the array sorted return Math.min(dp[N][1], dp[N][2], dp[N][3]); } // Driver code const arr = [2, 1, 3, 2, 1]; // Input array console.log(minOperations(arr)); // Output: 1 |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us