Count of jumps to reach the end of Array by jumping from arr[i] to arr[arr[i]]
Given an array arr[] of N integers, the task is to find the number of jumps required to escape the array arr[] for all values of i as the starting indices in the range [0, N) where the only possible jump from arr[i] is to arr[arr[i]] and escaping the array means arr[i]>=N, i.e, the index for the next jump does not exist.
Examples:
Input: arr[] = {2, 3, 4, 1, 10}
Output: 3 -1 2 -1 1
Explanation:
- For i = 0, initially the current index x is 0. After the 1st jump, the current index becomes x = arr[x] = arr[0] = 2. Similarly, after the 2nd jump, the current index becomes x = arr[2] = 4. After the 3rd jump x = arr[4] =10, which is greater than the array size. Therefore the number of steps required to escape the array is 3.
- For i = 1, initially the current index x is 1. After the 1st jump, x = arr[1] = 3. After the 2nd jump, x = arr[3] = 1, which has already been visited and hence forming a closed loop. Therefore it is impossible to escape the array from index 1.
Input: arr[] = {3, 12, 2, 7, 4, 10, 35, 5, 9, 27}
Output: 4 1 -1 3 -1 1 1 2 2 1
Approach: The given problem can be solved with the help of Recursion. Below are the steps to follow:
- Create an array visited[], which stores whether the current index has been visited already. Initially, visited = {0}.
- Create an array cntJumps[], which stores the number of jumps required for all indices in the range [0, N). Initially, cntJumps = {0}.
- Create a recursive function countJumps() which calculates the number of jumps required to escape the array from the current index.
- In the function countJumps(), if the answer of the current index is already calculated, return answer else if the current node is already visited, return -1 else if the array will be escaped after the jump from the current index, return 1.
- Recursively calculate the count of jumps after the current jump i.e, countJumps(i) = 1 + countJumps(arr[i]). Store the answers in the array cntJumps[].
- Print the array cntJumps[], which is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the number of jumps int cntJumps[100]; // Stores if the current index is visited int visited[100]; // Recursive function to find the number of // jumps to escape the array from index i int countJumps( int arr[], int N, int i) { // If the answer for the current index is // already calculated if (cntJumps[i] != 0) { return cntJumps[i]; } // If the current index is already visited if (visited[i]) { return -1; } // Mark current index as visited visited[i] = true ; // If the array is escaped after the jump // from the current index if (arr[i] >= N) { return cntJumps[i] = 1; } // Recursive call for the next jump int val = countJumps(arr, N, arr[i]); // If it is impossible to escape the array if (val == -1) cntJumps[i] = -1; else cntJumps[i] = 1 + val; // Return answer return cntJumps[i]; } // Function to print the number of jumps // required to escape the array from // ith index for all values of i in [0, N) void printCountJumps( int arr[], int N) { // Initialize visited array as 0 memset (visited, 0, sizeof (visited)); // Initialize cntJump array by 0 memset (cntJumps, 0, sizeof (cntJumps)); // Loop to iterate over all values of i for ( int i = 0; i < N; i++) { // If the index i is not visited already if (!visited[i]) { countJumps(arr, N, i); } } // Print Answer for ( int i = 0; i < N; i++) { cout << cntJumps[i] << " " ; } } // Driver Code int main() { int arr[] = { 3, 12, 2, 7, 4, 10, 35, 5, 9, 27 }; int N = sizeof (arr) / sizeof (arr[0]); printCountJumps(arr, N); return 0; } |
Java
// Java program for the above approach public class GFG { // Stores the number of jumps static int cntJumps[] = new int [ 100 ]; // Stores if the current index is visited static int visited[] = new int [ 100 ]; // Recursive function to find the number of // jumps to escape the array from index i static int countJumps( int arr[], int N, int i) { // If the answer for the current index is // already calculated if (cntJumps[i] != 0 ) { return cntJumps[i]; } // If the current index is already visited if (visited[i] != 0 ) { return - 1 ; } // Mark current index as visited visited[i] = 1 ; // If the array is escaped after the jump // from the current index if (arr[i] >= N) { cntJumps[i] = 1 ; return cntJumps[i]; } // Recursive call for the next jump int val = countJumps(arr, N, arr[i]); // If it is impossible to escape the array if (val == - 1 ) cntJumps[i] = - 1 ; else cntJumps[i] = 1 + val; // Return answer return cntJumps[i]; } // Function to print the number of jumps // required to escape the array from // ith index for all values of i in [0, N) static void printCountJumps( int arr[], int N) { // Initialize visited array as 0 for ( int i = 0 ; i < visited.length; i++) visited[i] = 0 ; // Initialize cntJump array by 0 for ( int i = 0 ; i < cntJumps.length; i++) cntJumps[i] = 0 ; // Loop to iterate over all values of i for ( int i = 0 ; i < N; i++) { // If the index i is not visited already if (visited[i] == 0 ) { countJumps(arr, N, i); } } // Print Answer for ( int i = 0 ; i < N; i++) { System.out.print(cntJumps[i] + " " ); } } // Driver Code public static void main (String[] args) { int arr[] = { 3 , 12 , 2 , 7 , 4 , 10 , 35 , 5 , 9 , 27 }; int N = arr.length; printCountJumps(arr, N); } } // This code is contributed by AnkThon |
Python3
# Python program for the above approach # Stores the number of jumps cntJumps = [ 0 for _ in range ( 100 )] # Stores if the current index is visited visited = [ 0 for _ in range ( 100 )] # Recursive function to find the number of # jumps to escape the array from index i def countJumps(arr, N, i): global visited global cntJumps # If the answer for the current index is # already calculated if (cntJumps[i] ! = 0 ): return cntJumps[i] # If the current index is already visited if (visited[i]): return - 1 # Mark current index as visited visited[i] = True # If the array is escaped after the jump # from the current index if (arr[i] > = N): cntJumps[i] = 1 return cntJumps[i] # Recursive call for the next jump val = countJumps(arr, N, arr[i]) # If it is impossible to escape the array if (val = = - 1 ): cntJumps[i] = - 1 else : cntJumps[i] = 1 + val # Return answer return cntJumps[i] # Function to print the number of jumps # required to escape the array from # ith index for all values of i in [0, N) def printCountJumps(arr, N): # Loop to iterate over all values of i for i in range ( 0 , N): # If the index i is not visited already if ( not visited[i]): countJumps(arr, N, i) # Print Answer for i in range ( 0 , N): print (cntJumps[i], end = " " ) # Driver Code if __name__ = = "__main__" : arr = [ 3 , 12 , 2 , 7 , 4 , 10 , 35 , 5 , 9 , 27 ] N = len (arr) printCountJumps(arr, N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; public class GFG { // Stores the number of jumps static int []cntJumps = new int [100]; // Stores if the current index is visited static int []visited = new int [100]; // Recursive function to find the number of // jumps to escape the array from index i static int countJumps( int []arr, int N, int i) { // If the answer for the current index is // already calculated if (cntJumps[i] != 0) { return cntJumps[i]; } // If the current index is already visited if (visited[i] != 0) { return -1; } // Mark current index as visited visited[i] = 1; // If the array is escaped after the jump // from the current index if (arr[i] >= N) { cntJumps[i] = 1; return cntJumps[i]; } // Recursive call for the next jump int val = countJumps(arr, N, arr[i]); // If it is impossible to escape the array if (val == -1) cntJumps[i] = -1; else cntJumps[i] = 1 + val; // Return answer return cntJumps[i]; } // Function to print the number of jumps // required to escape the array from // ith index for all values of i in [0, N) static void printCountJumps( int []arr, int N) { // Initialize visited array as 0 for ( int i = 0; i < visited.Length; i++) visited[i] = 0; // Initialize cntJump array by 0 for ( int i = 0; i < cntJumps.Length; i++) cntJumps[i] = 0; // Loop to iterate over all values of i for ( int i = 0; i < N; i++) { // If the index i is not visited already if (visited[i] == 0) { countJumps(arr, N, i); } } // Print Answer for ( int i = 0; i < N; i++) { Console.Write(cntJumps[i] + " " ); } } // Driver Code public static void Main ( string [] args) { int []arr = { 3, 12, 2, 7, 4, 10, 35, 5, 9, 27 }; int N = arr.Length; printCountJumps(arr, N); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for the above approach // Stores the number of jumps let cntJumps = new Array(100); // Stores if the current index is visited let visited = new Array(100); // Recursive function to find the number of // jumps to escape the array from index i function countJumps(arr, N, i) { // If the answer for the current index is // already calculated if (cntJumps[i] != 0) { return cntJumps[i]; } // If the current index is already visited if (visited[i]) { return -1; } // Mark current index as visited visited[i] = true ; // If the array is escaped after the jump // from the current index if (arr[i] >= N) { return (cntJumps[i] = 1); } // Recursive call for the next jump let val = countJumps(arr, N, arr[i]); // If it is impossible to escape the array if (val == -1) cntJumps[i] = -1; else cntJumps[i] = 1 + val; // Return answer return cntJumps[i]; } // Function to print the number of jumps // required to escape the array from // ith index for all values of i in [0, N) function printCountJumps(arr, N) { // Initialize visited array as 0 visited.fill(0); // Initialize cntJump array by 0 cntJumps.fill(0); // Loop to iterate over all values of i for (let i = 0; i < N; i++) { // If the index i is not visited already if (!visited[i]) { countJumps(arr, N, i); } } // Print Answer for (let i = 0; i < N; i++) { document.write(cntJumps[i] + " " ); } } // Driver Code let arr = [3, 12, 2, 7, 4, 10, 35, 5, 9, 27]; let N = arr.length; printCountJumps(arr, N); // This code is contributed by saurabh_jaiswal. </script> |
Output:
4 1 -1 3 -1 1 1 2 2 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us