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

Share Your Love

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:

  1. The given problem can be solved by finding the first i consecutive elements.
  2. Secondly, the first permutation is the same as the subsequence of the second permutation.
  3. 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.
  4. 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:

1

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

Share Your Love
Avatar photo
Lingaraj Senapati

Hey There! I am Lingaraj Senapati, the Founder of lingarajtechhub.com My skills are Freelance, Web Developer & Designer, Corporate Trainer, Digital Marketer & Youtuber.

Articles: 360

Newsletter Updates

Enter your email address below to subscribe to our newsletter