Myntra Software Development Engineer - Coding Question

Problem Description:

You are given a sequence X of length N + M, which is a permutation of 1 ... N + M.

An operation constitutes the following:

Pick i such that 1 <= i <= N, and j such that 1 <= j <= M. Then, swap X[i] and X[N + j].

You need to sort X in ascending order by applying the above mentioned operation any number of times.

Find what is the minimum number of swap operations needed to do so.

Constraints:

1 <= N, M <= 110

1 <= X[i] <= N + M

Input Format:

N M

X[1] X[2] ... X[N + M]

Output Format:

Print minimum number of swap operations that can be applied to X to sort it in ascending order.

Example:

N = 3 M = 2

X = [2 1 5 4 3]

For the above example, the minimum number of swaps required = 4

Explanation:

Following operations can be applied - 

1. i = 3, j = 2, X = [2 1 3 4 5]

2. i = 2, j = 1, X = [2 4 3 1 5]

3. i = 1, j = 1, X = [1 4 3 2 5]

4. i = 2, j = 1, X = [1 2 3 4 5]

Test Cases:

Input:

N = 3 M = 2

X = [2 1 5 4 3]

Output:

4

Input:

N = 1 M = 1

X = [1 1]

Output:

0