Encuentre el índice después de atravesar una array de permutación de 1 a N en K pasos

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:
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:
 

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  K \% N  y finalmente encontrar el índice después del  K \% N  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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *