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; }
0 Comments