Count number of ways to jump to reach end
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”.
Examples:
Input : {3, 2, 0, 1} Output : 2 1 1 0 For 3 number of steps or jumps that can be taken are 1, 2 or 3. The different ways are: 3 > 2 > 1 3 > 1 For 2 number of steps or jumps that can be taken are 1, or 2. The different ways are: 2 > 1 For 0 number of steps or jumps that can be taken are 0. One cannot move forward from this point. For 1 number of steps or jumps that can be taken are 1. But the element is at the end so no jump is required. Input : {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9} Output : 52 52 28 16 8 1 1 4 2 1 0
The solution is a modified version of the solution to the problem of Minimum number of jumps to reach end(Method 3).
This problem aims to count the different ways to jump from each element so as to reach to the end. For each element the count is being calculated by adding the counts of all those forward elements that can reach to the end and to which the current element could reach + 1(if the element can directly reach to the end).
Algorithm:
countWays(arr, n) Initialize array count_jump[n] = {0} count_jump[n1] = 0 for i = n2 to 0 if arr[i] >= (ni1) count_jump[i]++ for j=i+1; j < n1 && j <= arr[i]+i; i++ if count_jump[j] != 1 count_jump[i] += count_jump[j] if count_jump[i] == 0 count_jump[i] = 1 for i = 0 to n1 print count_jump[i]

// C++ implementation to count number
// of ways to jump to reach end
#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=n2; 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 < n1 && 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
ai=0; i<n; i++)
cout << count_jump[i] <<
" "
;
}
// Driver program to test above
int
main()
{
int
arr[] = {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9};
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
countWaysToJump(arr, n);
return
0;
}
Output:
52 52 28 16 8 1 1 4 2 1 0
Time Complexity: O(n^{2}) in worst case.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide