Minimum Swaps 2

Problem Statement :

```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)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [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  <=   n  <=  10^5
1  <=   arr[i]  <=  n

Sample Input 0

4
4 3 1 2

Sample Output 0

3```

Solution :

```                        ```Solution in C++ :

In   C++ :

vector<int>v[100003];
bool visit[100003];

int dfs(int i)
{
visit[i] = true;
int z = 1;

for(auto x: v[i])
if(!visit[x])
z += dfs(x);

return z;
}

int minimumSwaps(vector<int> A) {

for(int i = 0; i < A.size(); ++i )
v[i].push_back(A[i]-1), v[A[i]-1].push_back(i);

int c = 0;

for(int i = 0; i < A.size(); ++i)
{
if(!visit[i])
c += dfs(i) - 1;
}

return c;
}```
```

```                        ```Solution in Java :

In   Java  :

static int minimumSwaps(int[] a) {
int swap=0;
for(int i=0;i<a.length;i++){
if(i+1!=a[i]){
int t=i;
while(a[t]!=i+1){
t++;
}
int temp=a[t];
a[t]=a[i];
a[i]=temp;
swap++;
}
}
return swap;

}```
```

```                        ```Solution in Python :

In   Python3  :

def minimumSwaps(arr):
ref_arr = sorted(arr)
index_dict = {v: i for i,v in enumerate(arr)}
swaps = 0

for i,v in enumerate(arr):
correct_value = ref_arr[i]
if v != correct_value:
to_swap_ix = index_dict[correct_value]
arr[to_swap_ix],arr[i] = arr[i], arr[to_swap_ix]
index_dict[v] = to_swap_ix
index_dict[correct_value] = i
swaps += 1

return swaps```
```

Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element