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 Code int 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 approach 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 Code public 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 Code if __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 approach using 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 Code public 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.length document.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!