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