Convert an array into another by repeatedly removing the last element and placing it at any arbitrary index

Convert an array into another by, Suppose there are two arrays A[] and B[], both developed of a permutation of first N natural numbers, then 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.

Example:

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.

Explanation:

The given problem can be solved by finding the first i consecutive elements.
Secondly, the first permutation is the same as the subsequence of the second permutation.
Thirdly, 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[].

Then, Below Is The Implementation Of the Above Approach In C++:

#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;
}

Python 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

Output:

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