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!
