Given an integer K and an index array arr[] of length N which contains elements in the range [1, N], the task is to find the index after traversing the array by K steps starting from the index 1.
Traversal of index array: In the traversal of the index array the next index to be visited is the value at the current index.Â
Examples:Â
Â
Input: arr[] = {3, 2, 4, 1}, K = 5Â
Output: 4Â
Explanation:Â
Traversal to the indices starting from index 1:Â
1 => 3 => 4 => 1 => 3 => 4Â
Finally, after K traversals the index is 4
Input: arr[] = {6, 5, 2, 5, 3, 2}, K = 2Â
Output: 5Â
Â
Â
Approach: The key observation in the problem is that after traversing the index array N times it repeats itself. Therefore, we can find the value of the 
and then finally find the index after traversal.
Below is the implementation of the above approach:
Â
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 timesint 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 Codeint 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 timespublic 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 codepublic 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 timesdef 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 codeif __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 timespublic 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 codepublic 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 timesfunction 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 Codevar n = 4, k = 5;var arr = [3, 2, 4, 1];Â
// Function Calldocument.write( findIndexAfterKTrav(arr, n, k));Â
// This code is contributed by itsok.</script> |
Output:Â
4
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
