Minimum Swaps 2

Problem

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

Example

$arr = [7, 1, 3, 2, 4, 5, 6]$

Perform the following steps:

i   arr                         swap (indices)
 [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
 [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
 [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
 [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
 [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
 [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

Function Description

Complete the function minimumSwaps in the editor below.

minimumSwaps has the following parameter(s):

int arr[n]: an unordered array of integers

Returns

int: the minimum number of swaps to sort the array Input Format

The first line contains an integer n, the size of arr. The second line contains n space-separated integers arr[i].

Constraints

$1 \leq n \leq 10^5$
$1 \leq arr[i] \leq n$

Sample Input 0
```
4
4 3 1 2
```
Sample Output 0
```
3
```
Explanation 0

Given array $arr = [4,3,1,2]$

After swapping (0,2) we get $arr = [1,3,4,2]$

After swapping (1,2) we get $arr = [1,4,3,2]$

After swapping (1,3) we get $arr = [1,2,3,4]$

So, we need a minimum of 3 swaps to sort the array in ascending order.

Sample Input 1

5
2 3 4 1 5

Sample Output 1

Sample Input 2

7
1 3 5 2 4 6 7

Sample Output 2

Solution

If the position of a[i] already coincides with i+1, then ignore
Otherwise change a[i] to the a[i]-1th position and stay in place until at position i-1 is a[i]

Code

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
// Complete the minimumSwaps function below.
int minimumSwaps(vector<int> arr) {
    int res = 0;
    for (int i=0;i<arr.size();i++)
    {
        if (arr[i]==i+1)
            continue;
        
        swap(arr[i],arr[arr[i]-1]);
        res++;
        i--;
    }
    return res;
}