Given a sorted array arr[] of size N, the task is to check if it is possible to reach the end of the given array from arr[1] by jumping either arr[i] + k – 1, arr[i] + k, or arr[i] + k + 1 in each move, where k represents the number of indices jumped in the previous move. Consider K = 1 initially. If it is possible, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {0, 1, 3, 5, 6, 8, 12, 17}
Output: Yes
Explanation:
Step 1: Take (k + 1 = 2) steps to move to index containing A[1] + 2 = 3
Step 2: Take (k = 2) steps to move to index containing A[2] + 2 = 5.
Step 3: Take (k + 1 = 3) steps to move to index containing A[3] + 3 = 8
Step 4: Take (k + 1 = 4) steps to move to index containing A[5] + 4 = 12
Step 4: Take (k + 1 = 5) steps to move to index containing A[6] + 5 = 17
Since the last array index contains 17, the end of the array is reached.Input: arr[] = {0, 1, 2, 3, 4, 8, 9, 11}
Output: No
Naive Approach: The idea is to use recursion. From index i, recursively move to index having value A[i] + K – 1, A[i] + K, or A[i] + K + 1, and check whether it is possible to reach the end. If there exist any path to reach the end then print “Yes” else print “No”.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. Create a 2D table memo[N][N] to store the memorized results. For any index (i, j), memo[i][j] denotes if it is possible to move from index i to end(N-1) and previously taken j steps. memo[i][j] = 1 denotes possible and memo[i][j] = 0 denotes not possible. Follow the steps to solve the problem:
- Create a memoized table memo[][] of size N*N.
- For any index (i, j) update the memo[][] table as per the following:
- If i equals (N – 1), return 1 as the end position is reached.
- If memo[i][j] is already calculated, then return memo[i][j].
- Check any index having A[i] + j, A[i] + j – 1 or A[i] + j + 1 value, and recursively check is it possible to reach end.
- Store the value in memo[i][j] and return the value.
- If it’s possible to reach the end, print “Yes”.
- Else, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 8// Utility function to check if it is// possible to move from index 1 to N-1int check(int memo[][N], int i, int j, int* A){ // memo[i][j]: Stores if it is // possible to move from index i // to end(N-1) previously j steps // Successfully reached end index if (i == N - 1) return 1; // memo[i][j] is already calculated if (memo[i][j] != -1) return memo[i][j]; // Check if there is any index // having value of A[i]+j-1, // A[i]+j or A[i]+j+1 int flag = 0, k; for (k = i + 1; k < N; k++) { // If A[k] > A[i] + j + 1, // can't make a move further if (A[k] - A[i] > j + 1) break; // It's possible to move A[k] if (A[k] - A[i] >= j - 1 && A[k] - A[i] <= j + 1) // Check is it possible to // move from index k // having previously taken // A[k] - A[i] steps flag = check(memo, k, A[k] - A[i], A); // If yes then break the loop if (flag) break; } // Store value of flag in memo memo[i][j] = flag; // Return memo[i][j] return memo[i][j];}// Function to check if it is possible// to move from index 1 to N-1void checkEndReach(int A[], int K){ // Stores the memoized state int memo[N][N]; // Initialize all values as -1 memset(memo, -1, sizeof(memo)); // Initially, starting index = 1 int startIndex = 1; // Function call if (check(memo, startIndex, K, A)) cout << "Yes"; else cout << "No";}// Driver Codeint main(){ int A[] = { 0, 1, 3, 5, 6, 8, 12, 17 }; int K = 1; // Function Call checkEndReach(A, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{static int N = 8;// Utility function to check if it is// possible to move from index 1 to N-1static int check(int[][] memo, int i, int j, int[] A){ // memo[i][j]: Stores if it is // possible to move from index i // to end(N-1) previously j steps // Successfully reached end index if (i == N - 1) return 1; // memo[i][j] is already calculated if (memo[i][j] != -1) return memo[i][j]; // Check if there is any index // having value of A[i]+j-1, // A[i]+j or A[i]+j+1 int flag = 0, k; for(k = i + 1; k < N; k++) { // If A[k] > A[i] + j + 1, // can't make a move further if (A[k] - A[i] > j + 1) break; // It's possible to move A[k] if (A[k] - A[i] >= j - 1 && A[k] - A[i] <= j + 1) // Check is it possible to // move from index k // having previously taken // A[k] - A[i] steps flag = check(memo, k, A[k] - A[i], A); // If yes then break the loop if (flag != 0) break; } // Store value of flag in memo memo[i][j] = flag; // Return memo[i][j] return memo[i][j];}// Function to check if it is possible// to move from index 1 to N-1static void checkEndReach(int A[], int K){ // Stores the memoized state int[][] memo = new int[N][N]; // Initialize all values as -1 for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { memo[i][j] = -1; } } // Initially, starting index = 1 int startIndex = 1; // Function call if (check(memo, startIndex, K, A) != 0) System.out.println("Yes"); else System.out.println("No");}// Driver Codepublic static void main(String[] args){ int[] A = { 0, 1, 3, 5, 6, 8, 12, 17 }; int K = 1; // Function Call checkEndReach(A, K);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approachN = 8# Utility function to check if it is# possible to move from index 1 to N-1def check(memo, i, j, A): # memo[i][j]: Stores if it is # possible to move from index i # to end(N-1) previously j steps # Successfully reached end index if (i == N - 1): return 1 # memo[i][j] is already calculated if (memo[i][j] != -1): return memo[i][j] # Check if there is any index # having value of A[i]+j-1, # A[i]+j or A[i]+j+1 flag = 0 for k in range(i + 1, N): # If A[k] > A[i] + j + 1, # can't make a move further if (A[k] - A[i] > j + 1): break # It's possible to move A[k] if (A[k] - A[i] >= j - 1 and A[k] - A[i] <= j + 1): # Check is it possible to # move from index k # having previously taken # A[k] - A[i] steps flag = check(memo, k, A[k] - A[i], A) # If yes then break the loop if (flag != 0): break # Store value of flag in memo memo[i][j] = flag # Return memo[i][j] return memo[i][j]# Function to check if it is possible# to move from index 1 to N-1def checkEndReach(A, K): # Stores the memoized state memo = [[0] * N] * N # Initialize all values as -1 for i in range(0, N): for j in range(0, N): memo[i][j] = -1 # Initially, starting index = 1 startIndex = 1 # Function call if (check(memo, startIndex, K, A) != 0): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': A = [ 0, 1, 3, 5, 6, 8, 12, 17 ] K = 1 # Function Call checkEndReach(A, K) # This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;class GFG{static int N = 8;// Utility function to check if it is// possible to move from index 1 to N-1static int check(int[,] memo, int i, int j, int[] A){ // memo[i][j]: Stores if it is // possible to move from index i // to end(N-1) previously j steps // Successfully reached end index if (i == N - 1) return 1; // memo[i][j] is already calculated if (memo[i, j] != -1) return memo[i, j]; // Check if there is any index // having value of A[i]+j-1, // A[i]+j or A[i]+j+1 int flag = 0, k; for(k = i + 1; k < N; k++) { // If A[k] > A[i] + j + 1, // can't make a move further if (A[k] - A[i] > j + 1) break; // It's possible to move A[k] if (A[k] - A[i] >= j - 1 && A[k] - A[i] <= j + 1) // Check is it possible to // move from index k // having previously taken // A[k] - A[i] steps flag = check(memo, k, A[k] - A[i], A); // If yes then break the loop if (flag != 0) break; } // Store value of flag in memo memo[i, j] = flag; // Return memo[i][j] return memo[i, j];}// Function to check if it is possible// to move from index 1 to N-1static void checkEndReach(int[] A, int K){ // Stores the memoized state int[,] memo = new int[N, N]; // Initialize all values as -1 for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { memo[i, j] = -1; } } // Initially, starting index = 1 int startIndex = 1; // Function call if (check(memo, startIndex, K, A) != 0) Console.WriteLine("Yes"); else Console.WriteLine("No");}// Driver Codepublic static void Main(){ int[] A = { 0, 1, 3, 5, 6, 8, 12, 17 }; int K = 1; // Function Call checkEndReach(A, K);}}// This code is contributed by akhilsaini |
Javascript
<script>// JavaScript program for the above approachlet N = 8;// Utility function to check if it is// possible to move from index 1 to N-1function check(memo, i, j, A){ // memo[i][j]: Stores if it is // possible to move from index i // to end(N-1) previously j steps // Successfully reached end index if (i == N - 1) return 1; // memo[i][j] is already calculated if (memo[i][j] != -1) return memo[i][j]; // Check if there is any index // having value of A[i]+j-1, // A[i]+j or A[i]+j+1 let flag = 0, k; for(k = i + 1; k < N; k++) { // If A[k] > A[i] + j + 1, // can't make a move further if (A[k] - A[i] > j + 1) break; // It's possible to move A[k] if (A[k] - A[i] >= j - 1 && A[k] - A[i] <= j + 1) // Check is it possible to // move from index k // having previously taken // A[k] - A[i] steps flag = check(memo, k, A[k] - A[i], A); // If yes then break the loop if (flag != 0) break; } // Store value of flag in memo memo[i][j] = flag; // Return memo[i][j] return memo[i][j];} // Function to check if it is possible// to move from index 1 to N-1function checkEndReach(A, K){ // Stores the memoized state let memo = new Array(N); // Loop to create 2D array using 1D array for(var i = 0; i < memo.length; i++) { memo[i] = new Array(2); } // Initialize all values as -1 for(let i = 0; i < N; i++) { for(let j = 0; j < N; j++) { memo[i][j] = -1; } } // Initially, starting index = 1 let startIndex = 1; // Function call if (check(memo, startIndex, K, A) != 0) document.write("Yes"); else document.write("No");}// Driver codelet A = [ 0, 1, 3, 5, 6, 8, 12, 17 ];let K = 1;// Function CallcheckEndReach(A, K);// This code is contributed by avijitmondal1998</script> |
Output:
Yes
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
