Horje
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)
    • 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

    Output

    3

    Time Complexity: O(N)
    Auxiliary Space: O(N)


    		 


    Reffered: https://www.geeksforgeeks.org

    Arrays

    Related
    Constructing Palindromic Arrays with First Element as X Constructing Palindromic Arrays with First Element as X
    Find sum of count of duplicate numbers in all subarrays of given array Find sum of count of duplicate numbers in all subarrays of given array
    Minimize the maximum value in array by incrementing and decrementing. Minimize the maximum value in array by incrementing and decrementing.
    Find triplet (i, j, k) to maximize (P * arr[i] + Q * arr[j] + R * arr[k]) Find triplet (i, j, k) to maximize (P * arr[i] + Q * arr[j] + R * arr[k])
    Minimum cost to convert all characters of given binary array equal Minimum cost to convert all characters of given binary array equal

    Type:
    		 Geek
    Category:
    		 Coding
    Sub Category:
    		 Tutorial
    Uploaded by:
    		 Admin
    Views:
    		 16



     

    Horje