Dado un entero K y una array de índice arr[] de longitud N que contiene elementos en el rango [1, N], la tarea es encontrar el índice después de recorrer la array en K pasos a partir del índice 1.
Recorrido de la array de índice : En el recorrido de la array de índices, el siguiente índice que se visitará es el valor en el índice actual.
Ejemplos:
Entrada: arr[] = {3, 2, 4, 1}, K = 5
Salida: 4
Explicación:
Recorrido a los índices a partir del índice 1:
1 => 3 => 4 => 1 => 3 => 4
Finalmente , después de K recorridos, el índice es 4
Entrada: arr[] = {6, 5, 2, 5, 3, 2}, K = 2
Salida: 5
Enfoque: La observación clave en el problema es que después de atravesar la array de índices N veces, se repite. Por lo tanto, podemos encontrar el valor de y finalmente encontrar el índice después del recorrido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the // index after traversing the index // array K times #include<bits/stdc++.h> using namespace std; // Function to find the index after // traversing the index array K times int findIndexAfterKTrav(vector<int> arr, int n, int k){ k = k % n; int indi = 1; // Loop to traverse the index // array K times while (k){ indi = arr[indi-1]; k--; } return arr[indi-1]; } // Driver Code int main() { int n = 4, k = 5; vector<int> arr{3, 2, 4, 1}; // Function Call cout << findIndexAfterKTrav(arr, n, k); return 0; }
Java
// Java implementation to find the // index after traversing the index // array K times class GFG{ // Function to find the index after // traversing the index array K times public static int findIndexAfterKTrav(int[] arr, int n, int k) { k = k % n; int indi = 1; // Loop to traverse the index // array K times while (k > 0) { indi = arr[indi - 1]; k--; } return arr[indi - 1]; } // Driver code public static void main(String[] args) { int n = 4, k = 5; int[] arr = { 3, 2, 4, 1 }; // Function Call System.out.print(findIndexAfterKTrav(arr, n, k)); } } // This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to find the # index after traversing the index # array K times # Function to find the index after # traversing the index array K times def findIndexAfterKTrav(arr, n, k): k = k % n; indi = 1; # Loop to traverse the index # array K times while (k > 0): indi = arr[indi - 1]; k -= 1; return arr[indi - 1]; # Driver code if __name__ == '__main__': n = 4; k = 5; arr = [ 3, 2, 4, 1 ]; # Function Call print(findIndexAfterKTrav(arr, n, k)); # This code is contributed by Princi Singh
C#
// C# implementation to find the // index after traversing the index // array K times using System; class GFG{ // Function to find the index after // traversing the index array K times public static int findIndexAfterKTrav(int[] arr, int n, int k) { k = k % n; int indi = 1; // Loop to traverse the index // array K times while (k > 0) { indi = arr[indi - 1]; k--; } return arr[indi - 1]; } // Driver code public static void Main(String[] args) { int n = 4, k = 5; int[] arr = { 3, 2, 4, 1 }; // Function Call Console.Write(findIndexAfterKTrav(arr, n, k)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript implementation to find the // index after traversing the index // array K times // Function to find the index after // traversing the index array K times function findIndexAfterKTrav(arr, n, k) { k = k % n; var indi = 1; // Loop to traverse the index // array K times while (k){ indi = arr[indi-1]; k--; } return arr[indi-1]; } // Driver Code var n = 4, k = 5; var arr = [3, 2, 4, 1]; // Function Call document.write( findIndexAfterKTrav(arr, n, k)); // This code is contributed by itsok. </script>
4
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA