Учитывая целое число K и массив индексов arr [] длины N, который содержит элементы в диапазоне [1, N], задача состоит в том, чтобы найти индекс после обхода массива за K шагов, начиная с индекса 1.
Обход индексного массива: при обходе индексного массива следующий индекс, который нужно посетить, - это значение в текущем индексе.
Примеры:
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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
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++
#include<bits/stdc++.h>
using namespace std;
int findIndexAfterKTrav(vector<int> arr,
int n, int k){
k = k % n;
int indi = 1;
while (k){
indi = arr[indi-1];
k--;
}
return arr[indi-1];
}
int main() {
int n = 4, k = 5;
vector<int> arr{3, 2, 4, 1};
cout << findIndexAfterKTrav(arr, n, k);
return 0;
}
|
Java
class GFG{
public static int findIndexAfterKTrav(int[] arr,
int n, int k)
{
k = k % n;
int indi = 1;
while (k > 0)
{
indi = arr[indi - 1];
k--;
}
return arr[indi - 1];
}
public static void main(String[] args)
{
int n = 4, k = 5;
int[] arr = { 3, 2, 4, 1 };
System.out.print(findIndexAfterKTrav(arr, n, k));
}
}
|
Python3
def findIndexAfterKTrav(arr, n, k):
k = k % n;
indi = 1;
while (k > 0):
indi = arr[indi - 1];
k -= 1;
return arr[indi - 1];
if __name__ == "__main__":
n = 4;
k = 5;
arr = [ 3, 2, 4, 1 ];
print(findIndexAfterKTrav(arr, n, k));
|
C#
using System;
class GFG{
public static int findIndexAfterKTrav(int[] arr,
int n, int k)
{
k = k % n;
int indi = 1;
while (k > 0)
{
indi = arr[indi - 1];
k--;
}
return arr[indi - 1];
}
public static void Main(String[] args)
{
int n = 4, k = 5;
int[] arr = { 3, 2, 4, 1 };
Console.Write(findIndexAfterKTrav(arr, n, k));
}
}
|
Javascript
<script>
function findIndexAfterKTrav(arr, n, k)
{
k = k % n;
var indi = 1;
while (k){
indi = arr[indi-1];
k--;
}
return arr[indi-1];
}
var n = 4, k = 5;
var arr = [3, 2, 4, 1];
document.write( findIndexAfterKTrav(arr, n, k));
</script>
|