HackerRank Recursion: Davis’ Staircase problem solution

In this HackerRank Recursion: Davis’ Staircase Interview preparation kit problem you have Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase, module 10 power 10 + 7 on a new line.

Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the stepPerms function below.
def stepPerms(n):
    steps = [1, 2, 3]
    ways = dict()

    def climb(n, steps, ways):
        ret = 0
        for step in steps:
            if n - step == 0:
                ret += 1
            elif n - step > 0:
                if n - step not in ways:
                    ways[n - step] = climb(n - step, steps, ways)
                print(ways[n - step])
                ret += ways[n - step]
        return ret
    
    return climb(n, steps, ways)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = int(input())

    for s_itr in range(s):
        n = int(input())

        res = stepPerms(n)

        fptr.write(str(res) + 'n')

    fptr.close()

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

 class Solution {

    public static class Matrix{
    static int n;
     public   Matrix(int n)
        {
            this.n=n;
        }
        
    static long[][] multiply(long[][] a ,long[][] b)
    {
        long[][] ans=new long[n][n];
        
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                ans[i][j]=0;
                for(int k=0;k<n;k++)
                    ans[i][j]+=a[i][k]*b[k][j];
            }
        return ans;
    }
    static void print(long[][] a)
    {
        for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                    System.out.print(a[i][j]+" ");
                System.out.println();
            }
    }
    //Matrix Exponentiation
    static long MatrixExpo(long[][] base ,int power )
    {
       // print(base);
       
       //base cases
        if(power<=0) return 0;
        if(power==1) return 1;
        if(power==2) return 2;
        if(power==3) return 4;
        
        power-=3;
       
        long[][] ans=new long[n][n];
           
           //Make Answer-matrix
         for(int i=1;i<n;i++)
            for(int j=0;j<n;j++)  ans[i][j]=0;
        ans[0][0]=4;ans[0][1]=2;ans[0][2]=1;
     
     //Left-handside matrix
     //4 2 1
     //0 0 0
     //0 0 0
            while(power>0)
            {
                if(power%2==1)
                    ans=multiply(ans ,base);
                power=power/2;
                base=multiply(base ,base);
                
            }
        //return final answer F(n)  
        return ans[0][0];
    }
    
        
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        long[][] m=new long[3][3];
        //1 1 0
        //1 0 1
        //1 0 0
        m[0][0]=m[1][0]=m[2][0]=1;m[0][1]=1;m[0][2]=0;
        m[1][1]=0;m[1][2]=1;m[2][1]=0;m[2][2]=0;
        
        for(int a0 = 0; a0 < s; a0++){
            int n = in.nextInt();
            Matrix mat= new Matrix(3);
            System.out.println(Matrix.MatrixExpo(m ,n));
        }
    }
}

Problem solution in C++ programming.

#include <bits/stdc++.h>
#define MOD 10000000007
using namespace std;
int dp[100001], n;

int count_paths(int i) {

    if(i == 0)
        return 1;
    if(i < 0)
        return 0;
    if(dp[i] != -1)
        return dp[i];
    dp[i] = count_paths(i - 1) % MOD;
    dp[i] = (dp[i] + count_paths(i - 2)) % MOD;
    dp[i] = (dp[i] + count_paths(i - 3)) % MOD;
    return dp[i];
}

int main() {

    int t;
    cin >> t;
    assert(t >=1 and t<= 5);
    for(int i = 0; i < t; i++) {
        cin >> n;
        assert(n >= 1 and n <= 100000);
        memset(dp, -1, sizeof dp);
        int ans = count_paths(n);
        cout << ans << endl;
    }

    return 0;
}