Count of jumps to reach the end of Array by jumping from arr[i] to arr[arr[i]] - Coding

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)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Maximum subset sum having difference between its maximum and minimum in range [L, R]
Java Program To Recursively Remove All Adjacent Duplicates
Python Program To Recursively Remove All Adjacent Duplicates
Javascript Program For Swapping Kth Node From Beginning With Kth Node From End In A Linked List
Python Program for Leaders in an array

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	9