QUESTION

Given an array of numbers where each element represents the max number of jumps that can be made forward from that element. For each array element, count number of ways jumps can be made from that element to reach the end of the array. If an element is 0, then move cannot be made through that element. The element that cannot reach to the end should have a count -1.

“TESTCASE_1”: “5\n6 8 9 2 1\n###—###SEPERATOR—###—\n8 4 2 1 0”, “TESTCASE_2”: “6\n1 2 3 4 5 6\n###—###SEPERATOR—###—\n6 6 4 2 1 0”, “TESTCASE_3”: “7\n1 23 56 4 8 45 32\n###—###SEPERATOR—###—\n16 16 8 4 2 1 0”, “TESTCASE_4”: “11\n1 3 5 8 9 1 0 7 6 8 9\n###—###SEPERATOR—###—\n52 52 28 16 8 -1 -1 4 2 1 0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// function to count ways to jump to
// reach end for each array element
void countWaysToJump(int arr[], int n)
{
    // count_jump[i] store number of ways
    // arr[i] can reach to the end
    int count_jump[n];
    memset(count_jump, 0, sizeof(count_jump));
 
    // Last element does not require to jump.
    // Count ways to jump for remaining
    // elements
    for (int i=n-2; i>=0; i--)
    {
        // if the element can directly
        // jump to the end
        if (arr[i] >= n - i - 1)
            count_jump[i]++;
 
        // add the count of all the elements
        // that can reach to end and arr[i] can
        // reach to them
        for (int j=i+1; j < n-1 && j <= arr[i] + i; j++)
 
            // if element can reach to end then add
            // its count to count_jump[i]
            if (count_jump[j] != -1)
                 count_jump[i] += count_jump[j];
 
        // if arr[i] cannot reach to the end
        if (count_jump[i] == 0)
            count_jump[i] = -1;
    }
 
    // print count_jump for each
    // array element
    for (int i=0; i<n; i++)
        cout << count_jump[i] << " ";
}
 
// Driver program to test above
int main()
{
  int n;
  cin>>n;
  int arr[n], i;
  for(i=0; i<n; i++)
    cin>>arr[i];
  
    
    countWaysToJump(arr, n);
    return 0;
}