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 | Java 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
import java . io . * ; class GFG { static int N = 8 ; static int check ( int [ ] [ ] memo , int i , int j , int [ ] A ) { if ( i == N - 1 ) return 1 ; if ( memo [ i ] [ j ] != - 1 ) return memo [ i ] [ j ] ; int flag = 0 , k ; for ( k = i + 1 ; k < N ; k ++ ) { if ( A [ k ] - A [ i ] > j + 1 ) break ; if ( A [ k ] - A [ i ] >= j - 1 && A [ k ] - A [ i ] <= j + 1 ) flag = check ( memo , k , A [ k ] - A [ i ] , A ) ; if ( flag != 0 ) break ; } memo [ i ] [ j ] = flag ; return memo [ i ] [ j ] ; } static void checkEndReach ( int A [ ] , int K ) { int [ ] [ ] memo = new int [ N ] [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { memo [ i ] [ j ] = - 1 ; } } int startIndex = 1 ; if ( check ( memo , startIndex , K , A ) != 0 ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } public static void main ( String [ ] args ) { int [ ] A = { 0 , 1 , 3 , 5 , 6 , 8 , 12 , 17 } ; int K = 1 ; checkEndReach ( A , K ) ; } }