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 code
def countWaysToJump ( arr , n ) : NEW_LINE INDENT count_jump = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] >= n - i - 1 ) : NEW_LINE INDENT count_jump [ i ] += 1 NEW_LINE DEDENT j = i + 1 NEW_LINE while ( j < n - 1 and j <= arr [ i ] + i ) : NEW_LINE INDENT if ( count_jump [ j ] != - 1 ) : NEW_LINE INDENT count_jump [ i ] += count_jump [ j ] NEW_LINE DEDENT j += 1 NEW_LINE DEDENT if ( count_jump [ i ] == 0 ) : NEW_LINE INDENT count_jump [ i ] = - 1 NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT print ( count_jump [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT arr = [ 1 , 3 , 5 , 8 , 9 , 1 , 0 , 7 , 6 , 8 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE countWaysToJump ( arr , n ) NEW_LINE