## Problem Statement

Given an integer N and **two permutation of length N(1 through N )**,the task is to convert first permutation to second permutation by following operations:

**Select the last number of first permutation****Insert it back in the first permutation at any arbitrary (except last position)**

Determine the **minimum number of transformations** required to convert first permutation to second permutation

**Example:**

**input:**

N=5

A=[1,2,3,4,5] B=[1,5,2,3,4]

* output:*1

**explanation:Insert 5 between 1&2,First permutation becomes->[1,5,2,3,4]**

* input:*N=3
A=[3,2,1]
B=[1,2,3]

* output:*2

* Approach:*if the topological order (

**sequence relationship**) of the first

**i**

**(continuous)**elements of first permutation meets the target replacement (

**requirements i.e sub sequence of second permutation**), then the answer must be less than or equal to

**n-i,**Because the last

**n-i**elements can be selected optimally & inserted in its proper position, and will not be selected the second time.Therefore to solve the problem, we can find the length of first

**i**continuous elements (

**1≤i≤N & i should start from 1st index**) of first permutation which is present as sub sequence in the second permutation & then subtracting that length from the original length of the array.

**illustration 1:**

Sequence |

*In the above example the first four*

**(continuous)**elements of the first permutation i.e(1,2,3,4) of length-4, forms sub sequence in second permutation. i.e it is in sequence relationship with the target permutation which means that the inserting

**(N-i)**elements optimally will give us the desired result.

So **i=4 & operations needed =(n-i)=>(5-4)=1. **

**illustration 2:**

Sequence |

In the above example only the first two **(continuous) **elements i.e(1 & 5) of first permutation forms sub sequence in second permutation.

So **i=2 & operations needed =(n-i)=>(5-2)=3. **

** ****Solution **

Below is the Java implementation of the above approach:

** Code**import java.io.*;

class Solution {

public static int minCount(int[] a, int[] b, int n)

{

int i = 0;

for (int j = 0; j < n; j++) {

// if element of A

// at position j is equal

// to element of B at position i

// then increase j by 1

if (a[i] == b[j]) {

i++;

}

}

return n - i;

}

// driver code

public static void main(String[] args)

{

int n = 5;

int[] a = { 1, 2, 3, 4, 5 };

int[] b = { 1, 5, 2, 3, 4 };

// function calling

System.out.println(minCount(a, b, n));

}

}

**Output:**

1

**Time Complexity:**O(n)

**Auxiliary Space:**O(1)

Feel free to comment if you have any doubt.

**For more Data structure and algorithms,computer science,programming,coding related problems search my website.**

Learn how to prepare for Information Technology Based companies here

## 0 Comments

Have any doubt ? contact us