Minimum moves required to change position with the given operation
Given two integers S and T and an array arr that contains elements from 1 to N in unsorted fashion. The task is to find the minimum number of moves to move Sth element to the Tth place in the array with the following operation:
A single move consists of the following
// Initially b[] = {1, 2, 3, ..., N} // arr[] is input array for (i = 1..n) temp[arr[i]] = b[i] b = temp
If not possible then print -1 instead.
Examples:
Input: S = 2, T = 1, arr[] = {2, 3, 4, 1}
Output: 3
N is 4 (size of arr[])
Move 1: b[] = {4, 1, 2, 3}
Move 2: b[] = {3, 4, 1, 2}
Move 3: b[] = {2, 3, 4, 1}
Input: S = 3, T = 4, arr[] = {1, 2, 3, 4}
Output: -1
N is 4 (Size of arr[])
Regardless of how many moves are made, the permutation would remain the same.
Approach: The important observation here is that we are only concerned with the position of a single element, and not the entire array. So at each move we move the element at position S to the position arr[S], until we reach Tth position.
Since there are at most N distinct places that we can reach, if we don’t reach T within N moves, it would mean we can never reach it.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the number of moves int minimumMoves( int n, int a[], int s, int t) { int i, x; x = s; for (i = 1; i <= n; i++) { if (x == t) break ; x = a[x]; } // Destination reached if (x == t) return i - 1; else return -1; } // Driver Code int main() { int s = 2, t = 1, i; int a[] = {-1, 2, 3, 4, 1}; int n = sizeof (a) / sizeof (a[0]); cout << minimumMoves(n, a, s, t); } |
Java
// Java implementation of the approach public class GFG{ // Function to return the number of moves static int minimumMoves( int n, int a[], int s, int t) { int i, x; x = s; for (i = 1 ; i <= n; i++) { if (x == t) break ; x = a[x]; } // Destination reached if (x == t) return i - 1 ; else return - 1 ; } // Driver Code public static void main(String []args){ int s = 2 , t = 1 , i; int a[] = {- 1 , 2 , 3 , 4 , 1 }; int n = a.length ; System.out.println(minimumMoves(n, a, s, t)); } // This code is contributed by Ryuga } |
Python3
# Python3 implementation of the approach # Function to return the number of moves def minimumMoves(n, a, s, t): x = s for i in range ( 1 , n + 1 ): # Destination reached if x = = t: return i - 1 x = a[x] return - 1 # Driver Code if __name__ = = "__main__" : s, t = 2 , 1 a = [ - 1 , 2 , 3 , 4 , 1 ] n = len (a) print (minimumMoves(n, a, s, t)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System; public class GFG{ // Function to return the number of moves static int minimumMoves( int n, int []a, int s, int t) { int i, x; x = s; for (i = 1; i <= n; i++) { if (x == t) break ; x = a[x]; } // Destination reached if (x == t) return i - 1; else return -1; } // Driver Code public static void Main(){ int s = 2, t = 1; int []a = {-1, 2, 3, 4, 1}; int n = a.Length ; Console.WriteLine(minimumMoves(n, a, s, t)); } // This code is contributed by inder_verma. } |
PHP
<?php // PHP implementation of the approach // Function to return the number of moves function minimumMoves( $n , $a , $s , $t ) { $i ; $x ; $x = $s ; for ( $i = 1; $i <= $n ; $i ++) { if ( $x == $t ) break ; $x = $a [ $x ]; } // Destination reached if ( $x == $t ) return $i - 1; else return -1; } // Driver Code $s = 2; $t = 1; $i ; $a = array (-1, 2, 3, 4, 1); $n = count ( $a ); echo minimumMoves( $n , $a , $s , $t ); // This code is contributed by inder_verma. ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the number of moves function minimumMoves(n, a, s, t) { let i, x; x = s; for (i = 1; i <= n; i++) { if (x == t) break ; x = a[x]; } // Destination reached if (x == t) return i - 1; else return -1; } let s = 2, t = 1; let a = [-1, 2, 3, 4, 1]; let n = a.length ; document.write(minimumMoves(n, a, s, t)); // This code is contributed by suresh07. </script> |
3