Dados dos enteros S y T y un arreglo arr que contiene elementos del 1 al N sin ordenar. La tarea es encontrar el número mínimo de movimientos para mover el elemento Sth al lugar Tth en la array con la siguiente operación:
Un solo movimiento consiste en lo siguiente
// Initially b[] = {1, 2, 3, ..., N} // arr[] is input array for (i = 1..n) temp[arr[i]] = b[i] b = temp
Si no es posible, imprima -1 en su lugar.
Ejemplos:
Entrada: S = 2, T = 1, arr[] = {2, 3, 4, 1}
Salida: 3
N es 4 (tamaño de arr[])
Mover 1: b[] = {4, 1, 2, 3}
Movimiento 2: b[] = {3, 4, 1, 2}
Movimiento 3: b[] = {2, 3, 4, 1}
Entrada: S = 3, T = 4, arr[] = {1 , 2, 3, 4}
Salida: -1
N es 4 (Tamaño de arr[])
Independientemente de cuántos movimientos se realicen, la permutación seguirá siendo la misma.
Enfoque: la observación importante aquí es que solo nos preocupa la posición de un solo elemento, y no la array completa. Entonces, en cada movimiento, movemos el elemento en la posición S a la posición arr[S] , hasta llegar a la posición T.
Dado que hay como máximo N lugares distintos a los que podemos llegar, si no llegamos a T en N movimientos, significaría que nunca podremos alcanzarlo.
A continuación se muestra la implementación del enfoque anterior:
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
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA