Given two positive integers L and R and a binary string S of size N, the task is to check if the end of the string is reached from the index 0 by a series of jumps of indices, say i such that S[i] is 0 jumps are allowed in the range [L, R]. If it is possible to reach, then print Yes. Otherwise, print No.
Examples:
Input: S = “011010”, L = 2, R = 3
Output: Yes
Explanation:
Following are the series of moves having characters at that indices as 0:
S[0](= 0) -> S[3](= 0) -> S[5](= 0) and S[5] is the end of the string S.
Therefore, print Yes.Input: S = “01101110”, L = 2, R = 3
Output: No
Approach: The above problem can be solved with the help of Dynamic Programming, the idea is to maintain 1D array, say dp[] where dp[i] will store the possibility of reaching the ith position and update each index accordingly. Below are the steps:
- Initialize an array, dp[] such that dp[i] stores whether any index i can be reached from index 0 or not. Update the value of dp[0] as 1 as it is the current standing index.
- Initialize a variable, pre as 0 that stores the number of indices from which the current index is reachable.
- Iterate over the range [1, N) and update the value of pre variable as follows:
- If the value of (i >= minJump), then increment the value of pre by dp[i – minJump].
- If the value of (i > maxJump), then decrement the value of pre by dp[i – maxJump – 1].
- If the value of pre is positive, then there is at least 1 index from which the current index is reachable. Therefore, update the value of dp[i] = 1, if the value of S[i] = 0.
- After completing the above steps, if the value of dp[N – 1] is positive, then print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to reach the end of the binary string// using the given jumpsbool canReach(string s, int L, int R){ // Stores the DP states vector<int> dp(s.length()); // Initial state dp[0] = 1; // Stores count of indices from which // it is possible to reach index i int pre = 0; // Traverse the given string for (int i = 1; i < s.length(); i++) { // Update the values of pre // accordingly if (i >= L) { pre += dp[i - L]; } // If the jump size is out of // the range [L, R] if (i > R) { pre -= dp[i - R - 1]; } dp[i] = (pre > 0) and (s[i] == '0'); } // Return answer return dp[s.length() - 1];}// Driver Codeint main(){ string S = "01101110"; int L = 2, R = 3; cout << (canReach(S, L, R) ? "Yes" : "No"); return 0;} |
Java
// Java program for the above approachpublic class GFG { // Function to check if it is possible // to reach the end of the binary string // using the given jumps static int canReach(String s, int L, int R) { // Stores the DP states int dp[] = new int[s.length()]; // Initial state dp[0] = 1; // Stores count of indices from which // it is possible to reach index i int pre = 0; // Traverse the given string for (int i = 1; i < s.length(); i++) { // Update the values of pre // accordingly if (i >= L) { pre += dp[i - L]; } // If the jump size is out of // the range [L, R] if (i > R) { pre -= dp[i - R - 1]; } if (pre > 0 && s.charAt(i) == '0') dp[i] = 1; else dp[i] = 0; } // Return answer return dp[s.length() - 1]; } // Driver Code public static void main (String[] args) { String S = "01101110"; int L = 2, R = 3; if (canReach(S, L, R) == 1) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by AnkThon |
Python3
# python program for the above approach# Function to check if it is possible# to reach the end of the binary string# using the given jumpsdef canReach(s, L, R): # Stores the DP states dp = [0 for _ in range(len(s))] # Initial state dp[0] = 1 # Stores count of indices from which # it is possible to reach index i pre = 0 # Traverse the given string for i in range(1, len(s)): # Update the values of pre # accordingly if (i >= L): pre += dp[i - L] # If the jump size is out of # the range [L, R] if (i > R): pre -= dp[i - R - 1] dp[i] = (pre > 0) and (s[i] == '0') # Return answer return dp[len(s) - 1]# Driver Codeif __name__ == "__main__": S = "01101110" L = 2 R = 3 if canReach(S, L, R): print("Yes") else: print("No") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG{ // Function to check if it is possible // to reach the end of the binary string // using the given jumps static int canReach(String s, int L, int R) { // Stores the DP states int[] dp = new int[s.Length]; // Initial state dp[0] = 1; // Stores count of indices from which // it is possible to reach index i int pre = 0; // Traverse the given string for (int i = 1; i < s.Length; i++) { // Update the values of pre // accordingly if (i >= L) { pre += dp[i - L]; } // If the jump size is out of // the range [L, R] if (i > R) { pre -= dp[i - R - 1]; } if (pre > 0 && s[i] == '0') dp[i] = 1; else dp[i] = 0; } // Return answer return dp[s.Length - 1]; } // Driver Code public static void Main() { String S = "01101110"; int L = 2, R = 3; if (canReach(S, L, R) == 1) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by Saurabh |
Javascript
<script> // JavaScript program for the above approach // Function to check if it is possible // to reach the end of the binary string // using the given jumps const canReach = (s, L, R) => { // Stores the DP states let dp = new Array(s.length).fill(1); // Stores count of indices from which // it is possible to reach index i let pre = 0; // Traverse the given string for (let i = 1; i < s.length; i++) { // Update the values of pre // accordingly if (i >= L) { pre += dp[i - L]; } // If the jump size is out of // the range [L, R] if (i > R) { pre -= dp[i - R - 1]; } dp[i] = (pre > 0) && (s[i] == '0'); } // Return answer return dp[s.length - 1]; } // Driver Code let S = "01101110"; let L = 2, R = 3; if (canReach(S, L, R)) document.write("Yes"); else document.write("No");// This code is contributed by rakeshsahni</script> |
Output:
No
Time Complexity: O(N)
Auxiliary Space: O(N)
