Check if it is possible to reach to the index with value K when start index is given
Given an array arr[] of N positive integers and two positive integers S and K, the task is to reach the position of the array whose value is K from index S. We can only move from current index i to index (i + arr[i]) or (i – arr[i]). If there is a way to reach the position of the array whose value is K then print “Yes” else print “No”.
Examples:
Input: arr[] = {4, 2, 3, 0, 3, 1, 2}, S = 5, K = 0.
Output: Yes
Explanation:
Initially we are standing at index 5 that is element 1 hence we can move one step forward or backward. Therefore, all possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3. Since it is possible to reach index 3 our output is yes.Input: arr[] = {0, 3, 2, 1, 2}, S = 2, K = 3
Output: No
Explanation:
There is no way to reach index 1 with value 3.
Method 1 – Using BFS The Breadth-first search(BFS) approach is discussed below:
- Consider start index S as the source node and insert it into the queue.
- While the queue is not empty do the following:
- Pop the element from the top of the queue say temp.
- If temp is already visited or it is array out of bound index then, go to step 1.
- Else mark it as visited.
- Now if temp is the index of the array whose value is K, then print “Yes”.
- Else take two possible destinations from temp to (temp + arr[temp]), (temp – arr[temp]) and push it into the queue.
- If the index with value K is not reached after the above steps then print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // BFS approach to check if traversal // is possible or not bool check(int arr[], int& s_start, int start, bool visited[], int size, int K) { queue<int> q; // Push start index into queue q.push(start); // Until queue is not empty while (!q.empty()) { // Top element of queue int front = q.front(); // Pop the topmost element q.pop(); // mark as visited visited[front] = true; if (arr[front] == K && front != s_start) { return true; } // Check for i + arr[i] if (front + arr[front] >= 0 && front + arr[front] < size && visited[front + arr[front]] == false) { q.push(front + arr[front]); } // Check for i - arr[i] if (front - arr[front] >= 0 && front - arr[front] < size && visited[front - arr[front]] == false) { q.push(front - arr[front]); } } return false; } // Function to check if index with value // K can be reached or not void solve(int arr[], int n, int start, int K) { // Initialize visited array bool visited[n] = { false }; // BFS Traversal bool ans = check(arr, start, start, visited, n, K); // Print the result if (ans) cout << "Yes"; else cout << "No"; } // Driver Code int main() { // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = sizeof(arr) / sizeof(arr[0]); // Function Call solve(arr, N, start, K); return 0; } |
Java
// Java program for the above approachimport java.util.*;class GFG{ // BFS approach to check if traversal // is possible or not static boolean check(int arr[], int s_start, int start, boolean visited[], int size, int K) { Queue<Integer> q = new LinkedList<Integer>(); // Push start index into queue q.add(start); // Until queue is not empty while (!q.isEmpty()) { // Top element of queue int front = q.peek(); // Pop the topmost element q.remove(); // mark as visited visited[front] = true; if (arr[front] == K && front != s_start) { return true; } // Check for i + arr[i] if (front + arr[front] >= 0 && front + arr[front] < size && visited[front + arr[front]] == false) { q.add(front + arr[front]); } // Check for i - arr[i] if (front - arr[front] >= 0 && front - arr[front] < size && visited[front - arr[front]] == false) { q.add(front - arr[front]); } } return false; } // Function to check if index with value // K can be reached or not static void solve(int arr[], int n, int start, int K) { // Initialize visited array boolean visited[] = new boolean[n]; // BFS Traversal boolean ans = check(arr, start, start, visited, n, K); // Print the result if (ans) System.out.print("Yes"); else System.out.print("No"); } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.length; // Function Call solve(arr, N, start, K); }}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program for the above approach # BFS approach to check if traversal # is possible or not def check(arr, s_start, start, visited, size, K): q = [] # Push start index into queue q.append(start) # Until queue is not empty while (len(q) != 0): # Top element of queue front = q[-1] # Pop the topmost element q.pop(0) # Mark as visited visited[front] = True if (arr[front] == K and front != s_start): return True # Check for i + arr[i] if (front + arr[front] >= 0 and front + arr[front] < size and visited[front + arr[front]] == False): q.append(front + arr[front]) # Check for i - arr[i] if (front - arr[front] >= 0 and front - arr[front] < size and visited[front - arr[front]] == False): q.append(front - arr[front]) return False # Function to check if index with value # K can be reached or not def solve(arr, n, start, K): # Initialize visited array visited = [False for i in range(n)] # BFS Traversal ans = check(arr, start, start, visited, n, K) # Print the result if (ans): print('Yes') else: print('No')# Driver Code if __name__=="__main__": # Given array arr[] arr = [ 3, 0, 2, 1, 2 ] # Given start and end start = 2 K = 0 N = len(arr) # Function Call solve(arr, N, start, K) # This code is contributed by rutvik_56 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// BFS approach to check if traversal// is possible or notstatic bool check(int []arr, int s_start, int start, bool []visited, int size, int K){ Queue<int> q = new Queue<int>(); // Push start index into queue q.Enqueue(start); // Until queue is not empty while (q.Count != 0) { // Top element of queue int front = q.Peek(); // Pop the topmost element q.Dequeue(); // mark as visited visited[front] = true; if (arr[front] == K && front != s_start) { return true; } // Check for i + arr[i] if (front + arr[front] >= 0 && front + arr[front] < size && visited[front + arr[front]] == false) { q.Enqueue(front + arr[front]); } // Check for i - arr[i] if (front - arr[front] >= 0 && front - arr[front] < size && visited[front - arr[front]] == false) { q.Enqueue(front - arr[front]); } } return false;}// Function to check if index with value// K can be reached or notstatic void solve(int []arr, int n, int start, int K){ // Initialize visited array bool []visited = new bool[n]; // BFS Traversal bool ans = check(arr, start, start, visited, n, K); // Print the result if (ans) Console.Write("Yes"); else Console.Write("No");}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.Length; // Function call solve(arr, N, start, K);}}// This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program for the above approach // BFS approach to check if traversal // is possible or not function check(arr, s_start, start, visited, size, K) { let q = []; // Push start index into queue q.push(start); // Until queue is not empty while (q.length > 0) { // Top element of queue let front = q[0]; // Pop the topmost element q.shift(); // mark as visited visited[front] = true; if (arr[front] == K && front != s_start) { return true; } // Check for i + arr[i] if (front + arr[front] >= 0 && front + arr[front] < size && visited[front + arr[front]] == false) { q.push(front + arr[front]); } // Check for i - arr[i] if (front - arr[front] >= 0 && front - arr[front] < size && visited[front - arr[front]] == false) { q.push(front - arr[front]); } } return false; } // Function to check if index with value // K can be reached or not function solve(arr, n, start, K) { // Initialize visited array let visited = new Array(n); // BFS Traversal let ans = check(arr, start, start, visited, n, K); // Print the result if (ans) document.write("Yes"); else document.write("No"); } // Given array arr[] let arr = [ 3, 0, 2, 1, 2 ]; // Given start and end let start = 2; let K = 0; let N = arr.length; // Function Call solve(arr, N, start, K);</script> |
Output
No
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 2 – Using DFS: The Depth-first search(DFS) approach is discussed below:
- Initialize an array visited[] to mark visited vertex as true.
- Start with the start index S and explore other index depth-wise using recursion.
- In each recursive call, we check if that index is valid or previously not visited. If not so, we return false.
- Else if that index value is K, we return true.
- Else mark that index as visited and process recursively for i + arr[i] and i – arr[i] from current index i.
- If any of the recursive calls return true, this means that we reach to index with value K is possible and we 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; // DFS approach to check if traversal // is possible or not bool check(int arr[], int& s_start, int start, bool visited[], int size, int K) { // Base cases if (start < 0 || start >= size || visited[start]) { return false; } // Check if start index value K if (arr[start] == K && start != s_start) { return true; } // Mark as visited visited[start] = true; // Check for both i + arr[i] // and i - arr[i] recursively return (check(arr, s_start, start + arr[start], visited, size, K) || check(arr, s_start, start - arr[start], visited, size, K)); } // Function to check if index with value // K can be reached or not void solve(int arr[], int n, int start, int K) { // Initialize visited array bool visited[n] = { false }; // DFS Traversal bool ans = check(arr, start, start, visited, n, K); // Print the result if (ans) cout << "Yes"; else cout << "No"; } // Driver Code int main() { // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = sizeof(arr) / sizeof(arr[0]); // Function Call solve(arr, N, start, K); return 0; } |
Java
// Java program for the above approach import java.util.Arrays; class GFG{ // DFS approach to check if traversal // is possible or not public static boolean check(int[] arr, int s_start, int start, boolean[] visited, int size, int K) { // Base cases if (start < 0 || start >= size || visited[start]) { return false; } // Check if start index value K if (arr[start] == K && start != s_start) { return true; } // Mark as visited visited[start] = true; // Check for both i + arr[i] // and i - arr[i] recursively return (check(arr, s_start, start + arr[start], visited, size, K) || check(arr, s_start, start - arr[start], visited, size, K)); } // Function to check if index with value // K can be reached or not public static void solve(int[] arr, int n, int start, int K) { // Initialize visited array boolean[] visited = new boolean[n]; Arrays.fill(visited, false); // DFS Traversal boolean ans = check(arr, start, start, visited, n, K); // Print the result if (ans) System.out.print("Yes"); else System.out.print("No"); } // Driver code public static void main(String[] args) { // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.length; // Function call solve(arr, N, start, K); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach # DFS approach to check if traversal # is possible or not def check(arr, s_start, start, visited, size, K): # Base cases if (start < 0 or start >= size or visited[start]): return False # Check if start index value K if (arr[start] == K and start != s_start): return True # Mark as visited visited[start] = True # Check for both i + arr[i] # and i - arr[i] recursively return (check(arr, s_start, start + arr[start], visited, size, K) or check(arr, s_start, start - arr[start], visited, size, K))# Function to check if index with value # K can be reached or not def solve(arr, n, start, K): # Initialize visited array visited = [False] * n # DFS Traversal ans = check(arr, start, start, visited, n, K) # Print the result if (ans): print("Yes") else: print("No")# Driver Code if __name__ == "__main__": # Given array arr[] arr = [ 3, 0, 2, 1, 2 ] # Given start and end start = 2 K = 0 N = len(arr) # Function call solve(arr, N, start, K)# This code is contributed by chitranayal |
C#
// C# program for the above approach using System;class GFG{ // DFS approach to check if traversal // is possible or not public static bool check(int[] arr, int s_start, int start, bool[] visited, int size, int K) { // Base cases if (start < 0 || start >= size|| visited[start]) { return false; } // Check if start index value K if (arr[start] == K && start != s_start) { return true; } // Mark as visited visited[start] = true; // Check for both i + arr[i] // and i - arr[i] recursively return (check(arr, s_start, start + arr[start], visited, size, K) || check(arr, s_start, start - arr[start], visited, size, K)); } // Function to check if index with value // K can be reached or not public static void solve(int[] arr, int n, int start, int K) { // Initialize visited array bool[] visited = new bool[n]; // DFS Traversal bool ans = check(arr, start, start, visited, n, K); // Print the result if (ans) Console.Write("Yes"); else Console.Write("No"); } // Driver codepublic static void Main(String[] args){ // Given array []arr int []arr = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.Length; // Function call solve(arr, N, start, K); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// DFS approach to check if traversal// is possible or notfunction check(arr, s_start, start, visited, size, K){ // Base cases if (start < 0 || start >= size || visited[start]) { return false; } // Check if start index value K if (arr[start] == K && start != s_start) { return true; } // Mark as visited visited[start] = true; // Check for both i + arr[i] // and i - arr[i] recursively return (check(arr, s_start, start + arr[start], visited, size, K) || check(arr, s_start, start - arr[start], visited, size, K));}// Function to check if index with value// K can be reached or notfunction solve(arr, n, start, K){ // Initialize visited array var visited = Array(n).fill(false); // DFS Traversal var ans = check(arr, start, start, visited, n, K); // Print the result if (ans) document.write("Yes"); else document.write("No");}// Driver Code// Given array arr[]var arr = [ 3, 0, 2, 1, 2 ];// Given start and endvar start = 2;var K = 0;var N = arr.length;// Function Callsolve(arr, N, start, K);// This code is contributed by rrrtnx.</script> |
Output
No
Time Complexity: O(N)
Auxiliary Space: O(N)
Method 3 : DFS (Efficient Method) : We will follow the steps mention below :
- As array contains only positive number, so each time using dfs multiply that number with -1 which confirms that we have visited that element before.
- Check if the given index element is same as K or not.
- Otherwise, call dfs by increasing start + arr[start] and by decreasing start – arr[start].
- In base case check if start is in range of array length and also check is it visited before or not.
Implementation of above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// DFS approach to check if traversal// is possible or notbool dfs(int arr[], int N, int start, int K){ // Base cases if (start < 0 || start >= N || arr[start] < 0) return false; // Marking visited arr[start] *= -1; // Checking is that the element we needed or not // otherwise making call for dfs again for different // positions return (abs(arr[start]) == K) || dfs(arr, N, start + arr[start], K) || dfs(arr, N, start - arr[start], K);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = sizeof(arr) / sizeof(arr[0]); // Function Call bool flag = dfs(arr, N, start, K); if (flag) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG { // DFS approach to check if traversal // is possible or not public static boolean dfs(int[] arr, int N, int start, int K) { // Base Cases if (start < 0 || start >= N || arr[start] < 0) return false; // Marking visited arr[start] *= -1; // Checking is that the element we needed or not // otherwise making call for dfs again for different // positions return (Math.abs(arr[start]) == K) || dfs(arr, N, start + arr[start], K) || dfs(arr, N, start - arr[start], K); } // Driver code public static void main(String[] args) { // Given array arr[] int arr[] = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.length; // Function call if (dfs(arr, N, start, K)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
# Python3 program for the above approach# DFS approach to check if traversal# is possible or notdef dfs(arr, N, start, K): # Base Cases if start < 0 or start >= N or arr[start] < 0: return False # Marking visited arr[start] *= -1 # Checking is that the element we needed or not # otherwise making call for dfs again for different positions return abs(arr[start]) == K or dfs(arr, N, start + arr[start], K) or dfs(arr, N, start - arr[start], K) # Given array arr[]arr = [ 3, 0, 2, 1, 2 ]# Given start and endstart = 2K = 0N = len(arr)# Function callif dfs(arr, N, start, K): print("Yes")else: print("No") # This code is contributed by divyesh072019. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // DFS approach to check if traversal // is possible or not static bool dfs(int[] arr, int N, int start, int K) { // Base Cases if (start < 0 || start >= N || arr[start] < 0) return false; // Marking visited arr[start] *= -1; // Checking is that the element we needed or not // otherwise making call for dfs again for different // positions return (Math.Abs(arr[start]) == K) || dfs(arr, N, start + arr[start], K) || dfs(arr, N, start - arr[start], K); } static void Main() { // Given array arr[] int[] arr = { 3, 0, 2, 1, 2 }; // Given start and end int start = 2; int K = 0; int N = arr.Length; // Function call if (dfs(arr, N, start, K)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by rameshtravel07. |
Javascript
<script> // Javascript program for the above approach // DFS approach to check if traversal // is possible or not function dfs(arr, N, start, K) { // Base Cases if (start < 0 || start >= N || arr[start] < 0) return false; // Marking visited arr[start] *= -1; // Checking is that the element we needed or not // otherwise making call for dfs again for different // positions return (Math.abs(arr[start]) == K) || dfs(arr, N, start + arr[start], K) || dfs(arr, N, start - arr[start], K); } // Given array arr[] let arr = [ 3, 0, 2, 1, 2 ]; // Given start and end let start = 2; let K = 0; let N = arr.length; // Function call if (dfs(arr, N, start, K)) document.write("Yes"); else document.write("No");// This code is contributed by mukesh07.</script> |
Output
No
Time Complexity : O(n)
Auxiliary Space : O(n), (Space is only used for recursion)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
