Given two arrays A[] and B[], both consisting of a permutation of first N natural numbers, the task is to count the minimum number of times the last array element is required to be shifted to any arbitrary position in the array A[] to make both the arrays A[] and B[] equal.
Examples:
Input: A[] = {1, 2, 3, 4, 5}, B[] = {1, 5, 2, 3, 4}
Output:1
Explanation:
Initially, the array A[] is {1, 2, 3, 4, 5}. After moving the last array element, i.e. 5, and placing them between arr[0] (= 1) and arr[1](= 2) modifies the array to {1, 5, 2, 3, 4}, which is the same as the array B[].
Therefore, the minimum number of operations required to convert the array A[] to B[] is 1.Input: A[] = {3, 2, 1}, B[] = {1, 2, 3}
Output: 2
Explanation:
Initially, the array A[] is {3, 2, 1}.
Operation 1: After moving the last array element, i.e. 1, to the beginning of the array, modifies the array to {1, 3, 2}.
Operation 2: After moving the last element of the array, i.e. 2 and placing them between the elements arr[0] (= 1) and arr[1] (= 3) modifies the array to {1, 2, 3}, which is the same as the array B[].
Therefore, the minimum number of operations required to convert the array A[] to B[] is 2.
Approach: The given problem can be solved by finding the first i consecutive elements of the first permutation which is the same as the subsequence of the second permutation, then the count of operations must be less at least (N – I), since the last (N – i) elements can be selected optimally and inserted at required indices. Therefore, (N – i) is the minimum number of steps required for the conversion of the array A[] to B[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to count the minimum number// of operations required to convert// the array A[] into array B[]int minCount(int A[], int B[], int N){ // Stores the index in the first // permutation A[] which is same // as the subsequence in B[] int i = 0; // Find the first i elements in A[] // which is a subsequence in B[] for (int j = 0; j < N; j++) { // If element A[i] // is same as B[j] if (A[i] == B[j]) { i++; } } // Return the count of // operations required return N - i;}// Driver Codeint main(){ int A[] = { 1, 2, 3, 4, 5 }; int B[] = { 1, 5, 2, 3, 4 }; int N = sizeof(A) / sizeof(A[0]); cout << minCount(A, B, N); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to count the minimum number// of operations required to convert// the array A[] into array B[]static int minCount(int A[], int B[], int N){ // Stores the index in the first // permutation A[] which is same // as the subsequence in B[] int i = 0; // Find the first i elements in A[] // which is a subsequence in B[] for(int j = 0; j < N; j++) { // If element A[i] // is same as B[j] if (A[i] == B[j]) { i++; } } // Return the count of // operations required return N - i;}// Driver Codepublic static void main (String[] args){ int A[] = { 1, 2, 3, 4, 5 }; int B[] = { 1, 5, 2, 3, 4 }; int N = A.length; System.out.println(minCount(A, B, N));}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to count the minimum number# of operations required to convert# the array A[] into array B[]def minCount(A, B, N): # Stores the index in the first # permutation A[] which is same # as the subsequence in B[] i = 0 # Find the first i elements in A[] # which is a subsequence in B[] for j in range(N): # If element A[i] # is same as B[j] if (A[i] == B[j]): i += 1 # Return the count of # operations required return N - i# Driver Codeif __name__ == '__main__': A = [ 1, 2, 3, 4, 5 ] B = [ 1, 5, 2, 3, 4 ] N = len(A) print(minCount(A, B, N)) # This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Function to count the minimum number// of operations required to convert// the array A[] into array B[]static int minCount(int[] A, int[] B, int N){ // Stores the index in the first // permutation A[] which is same // as the subsequence in B[] int i = 0; // Find the first i elements in A[] // which is a subsequence in B[] for(int j = 0; j < N; j++) { // If element A[i] // is same as B[j] if (A[i] == B[j]) { i++; } } // Return the count of // operations required return N - i;}// Driver Codepublic static void Main(string[] args){ int[] A = { 1, 2, 3, 4, 5 }; int[] B = { 1, 5, 2, 3, 4 }; int N = A.Length; Console.WriteLine(minCount(A, B, N));}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program for the above approach// Function to count the minimum number// of operations required to convert// the array A[] into array B[]function minCount(A, B, N){ // Stores the index in the first // permutation A[] which is same // as the subsequence in B[] var i = 0 // Find the first i elements in A[] // which is a subsequence in B[] for(let j = 0; j < N; j++){ // If element A[i] // is same as B[j] if (A[i] == B[j]) i += 1 } // Return the count of // operations required return N - i }// Driver Code var A = [ 1, 2, 3, 4, 5 ]var B = [ 1, 5, 2, 3, 4 ]N = A.lengthdocument.write(minCount(A, B, N)) // This code is contributed by AnkThon</script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!