Minimum number of swaps required to make an array sorted

A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers find the minimum number of swaps needed to sort the array.

[gist https://gist.github.com/vishnujayvel/9593128 ]

 

Example :

A[3]=  3 , 2 , 1

B[3]= 1, 2, 3

i=0 j=0

A[0]!=B[0]

So swap ++ ( Whenever you increment assume that A[i] is removed and appended at the end )

i++

Now i=1 j=0

A[1]!=B[0]

So swap++

i++

Now i=2 j=0

A[2]==B[0]

Now j++

i == n now and hence break the loop

No. of swaps = 2

(Hackerrank) Snakes and Ladders: The Quickest Way Up

Found this problem in graph theory section of hackerrank and had so much fun solving it 🙂

             https://www.hackerrank.com/challenges/the-quickest-way-up

Its about finding the least number of rolls of the die in which one can able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1) provided one has the power to get any number (1-6) on the die when one rolls it.

 Solution :

Connect vertex i with i+1,i+2,i+3,i+4,i+5,i+6 ( denoting that from square i you can move to square i+1(when you get 1 when rolling the die),i+2(when you get 2 when rolling the die) and so on)

Similarly consider the starting and ending square of ladder , starting and ending square of the snake as vertices in the graph considered

Apply Floyd warshall algorithm and find minimum distance between square 1 to 100.