Find position after K jumps from start of given Array where each jump is from i to arr[i]
Given an array arr[] of size N containing elements from 1 to N. Find the position after exactly K jumps from index 1 where the jump from ith index sends to arr[i] index.
Examples:
Input: arr[ ] = { 3, 2, 4,1 }, K = 5;
Output: 4
Explanation: Start from index 1 and go to position 3 -> 4 ->1 -> 3 -> 4Input: arr[ ] = { 3 , 2 , 1 }, K = 3
Output: 3
Explanation: Start from index 1 and go to position 3 -> 1 -> 3
Approach: This problem can be solved using map data structure. The motive is to find the cycle formed when jumps from 1 element to another are made. When a loop or a cycle is observed mark it visited and count number of jumps taken to repeat this position and store it in X using map and if it is visited again the next X jumps are the same. So take modulo from K = K % X.
- Initialize a map.
- Initialize a variable len = 0 and idx = 1.
- Take a while loop and run until value of K is greater than 0 or loop is detected.
- After loop is over subtract the loop len from K.
- Now, Take the remaining jumps.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to determine the position int LastElement( int arr[], int N, int K) { // Decrement all array values by 1 // so it is easy to jump for ( int i = 0; i < N; i++) { --arr[i]; } // Initialize the unordered Map unordered_map< int , int > visit; // Initialize elem and len int elem = 0, len = 0; // Traverse until K is not 0 //or loop is detected while (K and !visit[elem]) { // Store len in map visit[elem] = ++len; // Decrement K for a jump K--; // Jump from one element to another elem = arr[elem]; } // After loop is over, take modulo of K K = K % (len + 1 - visit[elem]); // Now traverse loop K times for ( int i = 1; i <= K; i++) { elem = arr[elem]; } // Lastly return the element return elem + 1; } // Driver code int main() { int arr[] = { 3, 2, 4, 1 }; int N = 4; int K = 5; int ans = LastElement(arr, N, K); cout << ans; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Function to determine the position static int LastElement( int arr[], int N, int K) { // Decrement all array values by 1 // so it is easy to jump for ( int i = 0 ; i < N; i++) { --arr[i]; } // Initialize the Map HashMap<Integer, Integer> visit = new HashMap<Integer, Integer>(); // Initialize elem and len int elem = 0 , len = 0 ; // Traverse until K is not 0 //or loop is detected while (K >= 0 && visit.get(elem) == null ) { // Store len in map visit.put(elem, ++len); // Decrement K for a jump K--; // Jump from one element to another elem = arr[elem]; } // After loop is over, take modulo of K K = K % (len + 1 - visit.get(elem)); // Now traverse loop K times for ( int i = 1 ; i <= K; i++) { elem = arr[elem]; } // Lastly return the element return elem + 1 ; } // Driver code public static void main (String[] args) { int arr[ ] = { 3 , 2 , 4 , 1 }; int N = 4 ; int K = 5 ; int ans = LastElement(arr, N, K); System.out.print(ans); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # Function to determine the position def LastElement(arr, N, K) : # Decrement all array values by 1 # so it is easy to jump for i in range (N): arr[i] - = 1 # Initialize the unordered Map visit = [ 0 ] * (N); # Initialize elem and len elem = 0 _len = 0 ; # Traverse until K is not 0 #or loop is detected while (K and not visit[elem]): # Store len in map visit[elem] = + + _len; # Decrement K for a jump K - = 1 # Jump from one element to another elem = arr[elem]; # After loop is over, take modulo of K K = K % (_len + 1 - visit[elem]); # Now traverse loop K times for i in range ( 1 , K + 1 ): elem = arr[elem]; # Lastly return the element return elem + 1 ; # Driver code arr = [ 3 , 2 , 4 , 1 ]; N = 4 ; K = 5 ; ans = LastElement(arr, N, K); print (ans); # This code is contributed by Saurabh jaiswal |
C#
/*package whatever //do not write package name here */ using System; using System.Collections.Generic; public class GFG { // Function to determine the position static int LastElement( int []arr, int N, int K) { // Decrement all array values by 1 // so it is easy to jump for ( int i = 0; i < N; i++) { --arr[i]; } // Initialize the Map Dictionary< int , int > visit = new Dictionary< int , int >(); // Initialize elem and len int elem = 0, len = 0; // Traverse until K is not 0 //or loop is detected while (K >= 0 && !visit.ContainsKey(elem)) { // Store len in map visit.Add(elem, ++len); // Decrement K for a jump K--; // Jump from one element to another elem = arr[elem]; } // After loop is over, take modulo of K K = K % (len + 1 - visit[elem]); // Now traverse loop K times for ( int i = 1; i <= K; i++) { elem = arr[elem]; } // Lastly return the element return elem + 1; } // Driver code public static void Main(String[] args) { int []arr = { 3, 2, 4, 1 }; int N = 4; int K = 5; int ans = LastElement(arr, N, K); Console.Write(ans); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function to determine the position function LastElement(arr, N, K) { // Decrement all array values by 1 // so it is easy to jump for (let i = 0; i < N; i++) { --arr[i]; } // Initialize the unordered Map let visit = new Array(N); // Initialize elem and len let elem = 0, len = 0; // Traverse until K is not 0 //or loop is detected while (K && !visit[elem]) { // Store len in map visit[elem] = ++len; // Decrement K for a jump K--; // Jump from one element to another elem = arr[elem]; } // After loop is over, take modulo of K K = K % (len + 1 - visit[elem]); // Now traverse loop K times for (let i = 1; i <= K; i++) { elem = arr[elem]; } // Lastly return the element return elem + 1; } // Driver code let arr = [3, 2, 4, 1]; let N = 4; let K = 5; let ans = LastElement(arr, N, K); document.write(ans); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(N)