Given a binary string str of length N and an integer K, the task is to find the minimum number of steps required to move from str[0] to str[N – 1] with the following moves:
- From an index i, the only valid moves are i + 1, i + 2 and i + K
- An index i can only be visited if str[i] = ‘1’
Examples:
Input: str = “101000011”, K = 5
Output: 3
str[0] -> str[2] -> str[7] -> str[8]
Input: str = “1100000100111”, K = 6
Output: -1
There is no possible path.
Input: str = “10101010101111010101”, K = 4
Output: 6
Approach: The idea is to use dynamic programming to solve the problem.
- It is given that for any index i, it is possible to move to an index i+1, i+2 or i+K.
- One of the three possibilities will give the required result which is the minimum number of steps to reach the end.
- Therefore, the dp[] array is created and is filled in a bottom-up manner.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// of steps to reach the endint minSteps(string str, int n, int k){ // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; // If the length is 2 or 3 then the end // can be reached in a single step if (n < 4) return 1; // For the other cases, solve the problem // using dynamic programming int dp[n]; // It requires no move from the // end to reach the end dp[n - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[n - 2] = 1; dp[n - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { // If the current index is not reachable if (str[i] == '0') continue; // To store the minimum steps required // from the current index int steps = INT_MAX; // If it is a valid move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = min(steps, dp[i + k]); if (str[i + 1] == '1') steps = min(steps, dp[i + 1]); if (str[i + 2] == '1') steps = min(steps, dp[i + 2]); // Update the minimum steps required starting // from the current index dp[i] = (steps == INT_MAX) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == INT_MAX) return -1; // Return the minimum steps required return dp[0];}// Driver codeint main(){ string str = "101000011"; int n = str.length(); int k = 5; cout << minSteps(str, n, k); return 0;} |
Java
// Java implementation of the approachclass GFG { final static int INT_MAX = Integer.MAX_VALUE ; // Function to return the minimum number // of steps to reach the end static int minSteps(String str, int n, int k) { // If the end can't be reached if (str.charAt(n - 1) == '0') return -1; // Already at the end if (n == 1) return 0; // If the length is 2 or 3 then the end // can be reached in a single step if (n < 4) return 1; // For the other cases, solve the problem // using dynamic programming int dp[] = new int[n]; // It requires no move from the // end to reach the end dp[n - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[n - 2] = 1; dp[n - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { // If the current index is not reachable if (str.charAt(i) == '0') continue; // To store the minimum steps required // from the current index int steps =INT_MAX ; // If it is a valiINT_MAXd move then update // the minimum steps required if (i + k < n && str.charAt(i + k) == '1') steps = Math.min(steps, dp[i + k]); if (str.charAt(i + 1) == '1') steps = Math.min(steps, dp[i + 1]); if (str.charAt(i + 2) == '1') steps = Math.min(steps, dp[i + 2]); // Update the minimum steps required starting // from the current index dp[i] = (steps == INT_MAX) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == INT_MAX) return -1; // Return the minimum steps required return dp[0]; } // Driver code public static void main(String[] args) { String str = "101000011"; int n = str.length(); int k = 5; System.out.println(minSteps(str, n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach import sysINT_MAX = sys.maxsize;# Function to return the minimum number # of steps to reach the end def minSteps(string , n, k) : # If the end can't be reached if (string[n - 1] == '0') : return -1; # Already at the end if (n == 1) : return 0; # If the length is 2 or 3 then the end # can be reached in a single step if (n < 4) : return 1; # For the other cases, solve the problem # using dynamic programming dp = [0] * n; # It requires no move from the # end to reach the end dp[n - 1] = 0; # From the 2nd last and the 3rd last # index, only a single move is required dp[n - 2] = 1; dp[n - 3] = 1; # Update the answer for every index for i in range(n - 4, -1, -1) : # If the current index is not reachable if (string[i] == '0') : continue; # To store the minimum steps required # from the current index steps = INT_MAX; # If it is a valid move then update # the minimum steps required if (i + k < n and string[i + k] == '1') : steps = min(steps, dp[i + k]); if (string[i + 1] == '1') : steps = min(steps, dp[i + 1]); if (string[i + 2] == '1') : steps = min(steps, dp[i + 2]); # Update the minimum steps required starting # from the current index dp[i] = steps if (steps == INT_MAX) else (1 + steps); # Cannot reach the end starting from str[0] if (dp[0] == INT_MAX) : return -1; # Return the minimum steps required return dp[0]; # Driver code if __name__ == "__main__" : string = "101000011"; n = len(string); k = 5; print(minSteps(string, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG { static int INT_MAX = int.MaxValue ; // Function to return the minimum number // of steps to reach the end static int minSteps(string str, int n, int k) { // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; // If the length is 2 or 3 then the end // can be reached in a single step if (n < 4) return 1; // For the other cases, solve the problem // using dynamic programming int []dp = new int[n]; // It requires no move from the // end to reach the end dp[n - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[n - 2] = 1; dp[n - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { // If the current index is not reachable if (str[i] == '0') continue; // To store the minimum steps required // from the current index int steps = INT_MAX ; // If it is a valiINT_MAXd move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = Math.Min(steps, dp[i + k]); if (str[i + 1] == '1') steps = Math.Min(steps, dp[i + 1]); if (str[i + 2] == '1') steps = Math.Min(steps, dp[i + 2]); // Update the minimum steps required starting // from the current index dp[i] = (steps == INT_MAX) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == INT_MAX) return -1; // Return the minimum steps required return dp[0]; } // Driver code public static void Main() { string str = "101000011"; int n = str.Length; int k = 5; Console.WriteLine(minSteps(str, n, k)); } }// This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach// Function to return the minimum number// of steps to reach the endfunction minSteps(str, n, k){ // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; // If the length is 2 or 3 then the end // can be reached in a single step if (n < 4) return 1; // For the other cases, solve the problem // using dynamic programming var dp = Array(n); // It requires no move from the // end to reach the end dp[n - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[n - 2] = 1; dp[n - 3] = 1; // Update the answer for every index for (var i = n - 4; i >= 0; i--) { // If the current index is not reachable if (str[i] == '0') continue; // To store the minimum steps required // from the current index var steps = 1000000000; // If it is a valid move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = Math.min(steps, dp[i + k]); if (str[i + 1] == '1') steps = Math.min(steps, dp[i + 1]); if (str[i + 2] == '1') steps = Math.min(steps, dp[i + 2]); // Update the minimum steps required starting // from the current index dp[i] = (steps == 1000000000) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == 1000000000) return -1; // Return the minimum steps required return dp[0];}// Driver codevar str = "101000011";var n = str.length;var k = 5;document.write( minSteps(str, n, k));// This code is contributed by famously.</script> |
Output
3
Time Complexity: O(N) where N is the length of the string.
Auxiliary Space: O(N) as it is using extra space for array “dp”
Efficient approach: Space optimization
To optimize space, we can use a rolling array of size k instead of an array of size n to store the dynamic programming values. Since we only need to access values up to k positions ahead, we can reuse the same array to store values for the next iteration.
Implementation Steps:
- Create a function minSteps and initialize all base cases.
- Create a DP vector of size K.
- Iterate the array and update the answer for every index
- initialize a variable steps to store the minimum steps required from the current index.
- Now If it is a valid move then update the minimum steps required and update the steps accordingly.
- At last return minimum steps required if dp[0] is not INT_MAX else return -1.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Function to return the minimum number// of steps to reach the endint minSteps(string str, int n, int k){ // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; if (n < 4) return 1; // initialize dp of required size K int dp[k]; // It requires no move from the // end to reach the end dp[k - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[k - 2] = 1; dp[k - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { if (str[i] == '0') continue; // To store the minimum steps required // from the current index int steps = INT_MAX; // If it is a valid move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = min(steps, dp[(i + k) % k]); if (str[i + 1] == '1') steps = min(steps, dp[(i + 1) % k]); if (str[i + 2] == '1') steps = min(steps, dp[(i + 2) % k]); // Update the minimum steps required starting // from the current index dp[i % k] = (steps == INT_MAX) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == INT_MAX) return -1; // Return the minimum steps required return dp[0];}// Driver codeint main(){ string str = "101000011"; int n = str.length(); int k = 5; cout << minSteps(str, n, k); return 0;} |
Java
import java.util.*;class Main { public static void main(String[] args) { String str = "101000011"; int n = str.length(); int k = 5; System.out.println(minSteps(str, n, k)); } // Function to return the minimum number // of steps to reach the end public static int minSteps(String str, int n, int k) { // If the end can't be reached if (str.charAt(n - 1) == '0') return -1; // Already at the end if (n == 1) return 0; if (n < 4) return 1; // initialize dp of required size K int[] dp = new int[k]; // It requires no move from the // end to reach the end dp[k - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[k - 2] = 1; dp[k - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { if (str.charAt(i) == '0') continue; // To store the minimum steps required // from the current index int steps = Integer.MAX_VALUE; // If it is a valid move then update // the minimum steps required if (i + k < n && str.charAt(i + k) == '1') steps = Math.min(steps, dp[(i + k) % k]); if (str.charAt(i + 1) == '1') steps = Math.min(steps, dp[(i + 1) % k]); if (str.charAt(i + 2) == '1') steps = Math.min(steps, dp[(i + 2) % k]); // Update the minimum steps required starting // from the current index dp[i % k] = (steps == Integer.MAX_VALUE) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == Integer.MAX_VALUE) return -1; // Return the minimum steps required return dp[0]; }} |
Python3
import sys# Function to return the minimum number of steps to reach the enddef minSteps(str, n, k): # If the end can't be reached if str[n - 1] == '0': return -1 # Already at the end if n == 1: return 0 if n < 4: return 1 # initialize dp of required size K dp = [0] * k # It requires no move from the end to reach the end dp[k - 1] = 0 # From the 2nd last and the 3rd last index, only a single move is required dp[k - 2] = 1 dp[k - 3] = 1 # Update the answer for every index for i in range(n - 4, -1, -1): if str[i] == '0': continue # To store the minimum steps required from the current index steps = sys.maxsize # If it is a valid move then update the minimum steps required if i + k < n and str[i + k] == '1': steps = min(steps, dp[(i + k) % k]) if str[i + 1] == '1': steps = min(steps, dp[(i + 1) % k]) if str[i + 2] == '1': steps = min(steps, dp[(i + 2) % k]) # Update the minimum steps required starting from the current index dp[i % k] = (steps if steps == sys.maxsize else 1 + steps) # Cannot reach the end starting from str[0] if dp[0] == sys.maxsize: return -1 # Return the minimum steps required return dp[0]# Driver codestr = "101000011"n = len(str)k = 5print(minSteps(str, n, k)) |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the minimum number // of steps to reach the end static int minSteps(string str, int n, int k) { // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; if (n < 4) return 1; // initialize dp of required size K int []dp=new int[k]; // It requires no move from the // end to reach the end dp[k - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[k - 2] = 1; dp[k - 3] = 1; // Update the answer for every index for (int i = n - 4; i >= 0; i--) { if (str[i] == '0') continue; // To store the minimum steps required // from the current index int steps =int.MaxValue ; // If it is a valid move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = Math.Min(steps, dp[(i + k) % k]); if (str[i + 1] == '1') steps = Math.Min(steps, dp[(i + 1) % k]); if (str[i + 2] == '1') steps = Math.Min(steps, dp[(i + 2) % k]); // Update the minimum steps required starting // from the current index dp[i % k] = (steps == int.MaxValue) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == int.MaxValue) return -1; // Return the minimum steps required return dp[0]; } // Driver code public static void Main() { string str = "101000011"; int n = str.Length; int k = 5; Console.WriteLine(minSteps(str, n, k)); } }// This code is contributed by panwar2001 |
Javascript
function minSteps(str, n, k) { // If the end can't be reached if (str[n - 1] == '0') return -1; // Already at the end if (n == 1) return 0; if (n < 4) return 1; // initialize dp of required size K let dp = new Array(k); // It requires no move from the // end to reach the end dp[k - 1] = 0; // From the 2nd last and the 3rd last // index, only a single move is required dp[k - 2] = 1; dp[k - 3] = 1; // Update the answer for every index for (let i = n - 4; i >= 0; i--) { if (str[i] == '0') continue; // To store the minimum steps required // from the current index let steps = Number.MAX_SAFE_INTEGER; // If it is a valid move then update // the minimum steps required if (i + k < n && str[i + k] == '1') steps = Math.min(steps, dp[(i + k) % k]); if (str[i + 1] == '1') steps = Math.min(steps, dp[(i + 1) % k]); if (str[i + 2] == '1') steps = Math.min(steps, dp[(i + 2) % k]); // Update the minimum steps required starting // from the current index dp[i % k] = (steps == Number.MAX_SAFE_INTEGER) ? steps : 1 + steps; } // Cannot reach the end starting from str[0] if (dp[0] == Number.MAX_SAFE_INTEGER) return -1; // Return the minimum steps required return dp[0];}// Driver codelet str = "101000011";let n = str.length;let k = 5;console.log(minSteps(str, n, k)); |
Output
3
Time Complexity: O(N) where N is the length of the string.
Auxiliary Space: O(K)
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!
