Given an array arr[] of size N and an integer, K. Array represents the broken steps in a staircase. One can not reach a broken step. The task is to find the number of ways to reach the Kth step in the staircase starting from 0 when a step of maximum length 2 can be taken at any position. The answer can be very large. So, print the answer modulo 109 + 7.
Examples:
Input: arr[] = {3}, K = 6
Output: 4
0 -> 1 -> 2 -> 4 -> 5 -> 6
0 -> 1 -> 2 -> 4 -> 6
0 -> 2 -> 4 -> 5 -> 6
0 -> 2 -> 4 -> 6
Input: arr[] = {3, 4}, K = 6
Output: 0
Approach: This problem can be solved using dynamic programming. Create a dp[] array where dp[i] will store the number of ways to reach the ith step and the recurrence relation will be dp[i] = dp[i – 1] + dp[i – 2] only if the ith step is not broken otherwise 0. The final answer will be dp[K].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1000000007;// Function to return the number// of ways to reach the kth stepint number_of_ways(int arr[], int n, int k){ if (k == 1) return 1; // Create the dp array int dp[k + 1]; memset(dp, -1, sizeof dp); // Broken steps for (int i = 0; i < n; i++) dp[arr[i]] = 0; dp[0] = 1; dp[1] = (dp[1] == -1) ? 1 : dp[1]; // Calculate the number of ways for // the rest of the positions for (int i = 2; i <= k; ++i) { // If it is a blocked position if (dp[i] == 0) continue; // Number of ways to get to the ith step dp[i] = dp[i - 1] + dp[i - 2]; dp[i] %= MOD; } // Return the required answer return dp[k];}// Driver codeint main(){ int arr[] = { 3 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 6; cout << number_of_ways(arr, n, k); return 0;} |
Java
// Java implementation of the approach class GFG { static final int MOD = 1000000007; // Function to return the number // of ways to reach the kth step static int number_of_ways(int arr[], int n, int k) { if (k == 1) return 1; // Create the dp array int dp[] = new int[k + 1]; int i; for(i = 0; i < k + 1; i++) dp[i] = -1 ; // Broken steps for (i = 0; i < n; i++) dp[arr[i]] = 0; dp[0] = 1; dp[1] = (dp[1] == -1) ? 1 : dp[1]; // Calculate the number of ways for // the rest of the positions for (i = 2; i <= k; ++i) { // If it is a blocked position if (dp[i] == 0) continue; // Number of ways to get to the ith step dp[i] = dp[i - 1] + dp[i - 2]; dp[i] %= MOD; } // Return the required answer return dp[k]; } // Driver code public static void main (String[] args) { int arr[] = { 3 }; int n = arr.length; int k = 6; System.out.println(number_of_ways(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach MOD = 1000000007; # Function to return the number # of ways to reach the kth step def number_of_ways(arr, n, k) : if (k == 1) : return 1; # Create the dp array dp = [-1] * (k + 1); # Broken steps for i in range(n) : dp[arr[i]] = 0; dp[0] = 1; dp[1] = 1 if (dp[1] == -1) else dp[1]; # Calculate the number of ways for # the rest of the positions for i in range(2, k + 1) : # If it is a blocked position if (dp[i] == 0) : continue; # Number of ways to get to the ith step dp[i] = dp[i - 1] + dp[i - 2]; dp[i] %= MOD; # Return the required answer return dp[k]; # Driver code if __name__ == "__main__" : arr = [ 3 ]; n = len(arr); k = 6; print(number_of_ways(arr, n, k)); # This code is contributed by kanugargng |
C#
// C# implementation of the approach using System;class GFG { static readonly int MOD = 1000000007; // Function to return the number // of ways to reach the kth step static int number_of_ways(int []arr, int n, int k) { if (k == 1) return 1; // Create the dp array int []dp = new int[k + 1]; int i; for(i = 0; i < k + 1; i++) dp[i] = -1 ; // Broken steps for (i = 0; i < n; i++) dp[arr[i]] = 0; dp[0] = 1; dp[1] = (dp[1] == -1) ? 1 : dp[1]; // Calculate the number of ways for // the rest of the positions for (i = 2; i <= k; ++i) { // If it is a blocked position if (dp[i] == 0) continue; // Number of ways to get to the ith step dp[i] = dp[i - 1] + dp[i - 2]; dp[i] %= MOD; } // Return the required answer return dp[k]; } // Driver code public static void Main (String[] args) { int []arr = { 3 }; int n = arr.Length; int k = 6; Console.WriteLine(number_of_ways(arr, n, k)); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation of the approach let MOD = 1000000007; // Function to return the number // of ways to reach the kth step function number_of_ways(arr, n, k) { if (k == 1) return 1; // Create the dp array let dp = new Array(k + 1); let i; for(i = 0; i < k + 1; i++) dp[i] = -1 ; // Broken steps for (i = 0; i < n; i++) dp[arr[i]] = 0; dp[0] = 1; dp[1] = (dp[1] == -1) ? 1 : dp[1]; // Calculate the number of ways for // the rest of the positions for (i = 2; i <= k; ++i) { // If it is a blocked position if (dp[i] == 0) continue; // Number of ways to get to the ith step dp[i] = dp[i - 1] + dp[i - 2]; dp[i] %= MOD; } // Return the required answer return dp[k]; } let arr = [ 3 ]; let n = arr.length; let k = 6; document.write(number_of_ways(arr, n, k)); </script> |
Output:
4
Time Complexity: O(n)
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!
