Hello All,

I came across this interesting question in which there is an array consisting of n numbers with each number lying between 1 to m. Now it is asked to find the minimum number of swaps necessary to reformat the array such that the array elements with same value come together.

Note: Here Here swap means exchanging position of two adjacent numbers.

Example: If N=4 && M=2 && A[4]=1 2 1 2 => Ans=1

If N=6 && M=4 && A[6]=2 1 4 3 1 2 => Ans=6

Constraints: 1<=N<=10^5 && 1<=M<=16

I have been able to find that this question can be solved using DP+bitmasking but I am facing difficulty in forming the DP structure. So if anybody can help,it will be really grateful.

Thanks