Check if end of a sorted Array can be reached by repeated jumps of one more , one less or same number of indices as previous jump | Python3 program for the above approach ; Utility function to check if it is possible to move from index 1 to N - 1 ; Successfully reached end index ; memo [ i ] [ j ] is already calculated ; Check if there is any index having value of A [ i ] + j - 1 , A [ i ] + j or A [ i ] + j + 1 ; If A [ k ] > A [ i ] + j + 1 , can 't make a move further ; It 's possible to move A[k] ; Check is it possible to move from index k having previously taken A [ k ] - A [ i ] steps ; If yes then break the loop ; Store value of flag in memo ; Return memo [ i ] [ j ] ; Function to check if it is possible to move from index 1 to N - 1 ; Stores the memoized state ; Initialize all values as - 1 ; Initially , starting index = 1 ; Function call ; Driver Code ; Function Call
N = 8 NEW_LINE def check ( memo , i , j , A ) : NEW_LINE INDENT if ( i == N - 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( memo [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return memo [ i ] [ j ] NEW_LINE DEDENT flag = 0 NEW_LINE for k in range ( i + 1 , N ) : NEW_LINE INDENT if ( A [ k ] - A [ i ] > j + 1 ) : NEW_LINE break NEW_LINE if ( A [ k ] - A [ i ] >= j - 1 and A [ k ] - A [ i ] <= j + 1 ) : NEW_LINE flag = check ( memo , k , A [ k ] - A [ i ] , A ) NEW_LINE if ( flag != 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT memo [ i ] [ j ] = flag NEW_LINE return memo [ i ] [ j ] NEW_LINE DEDENT def checkEndReach ( A , K ) : NEW_LINE INDENT memo = [ [ 0 ] * N ] * N NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE memo [ i ] [ j ] = - 1 NEW_LINE DEDENT startIndex = 1 NEW_LINE if ( check ( memo , startIndex , K , A ) != 0 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 0 , 1 , 3 , 5 , 6 , 8 , 12 , 17 ] NEW_LINE K = 1 NEW_LINE checkEndReach ( A , K ) NEW_LINE DEDENT