This problem takes two forms. Both the forms differ by the meaning of the “swap” operation. In one form, a swap means “removing any element from the array and appending it to the back of the same array” and in another form, a swap means “removing any element from the array and placing it at the top(front) of the same array“. Below are the codes for both the forms.
1) Removing any element from the array and appending it to the back of the same array
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int n,i,last,j,swap=0;
scanf("%d",&n);
int a[n],b[n];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i]; // copy input array a to b
}
sort(b,b+n); // sorting the b array
j=0;
for(i=0;i<n;i++)
{
if(a[i]==b[j]) j++;
else swap++;
}
printf("%d\n",swap);
return 0;
}
2) Removing any element from the array and placing it at the top(front) of the same array
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int n,i,last,j,swap=0;
scanf("%d",&n);
int a[n],b[n];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i]; // copy input array a to b
}
sort(b,b+n); // sorting the b array
j=n-1;
for(i=n-1;i>=0;i--)
{
if(a[i]==b[j]) j--;
else swap++;
}
printf("%d\n",swap);
return 0;
}
The complexity of both the solutions in O(nlogn) ( O(nlogn) (for sorting) + O(n) (for finding the numbers of swaps ) = O(nlogn). If anyone have doubts, please do post comments.
nvkarthick8 
What’s the logic behind these solutions? I don’t get it. Please explain.
For example in the first case take the input:
6
1 4 2 5 6 3
Then the array b is
1 2 3 4 5 6
Now all elements except 1, 2 and 3 in the initial array a must be swapped because they definitely cant be there as some number to the right of each number is less than and even if you swap any number of numbers, those numbers will still remain the right of them. So the logic is to find the longest subsequence of the given array which is actually the initial elements of b. And then swap all other elements leaving these as it is.