I solved the quesiion " Given a floor of size n x m. Find the number of ways to tile the floor with tiles of size 1 x m . A tile can either be placed horizontally or vertically. "
using recursive approach. But the test cases are showing runtime error though in custom input the code is working fine.
My Code is as follows:
"
import java.util.;
import java.lang.;
import java.io.*;
class Main {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt(),m=sc.nextInt();
fun(n,m,0,0);
}
}
public static void fun(int n,int m,int count,int res){
if(n<=m){
if(n<m && count==0 && count<=n){
res=res+1;
System.out.println((res)%(long)(Math.pow(10,9)+7));
return;
}
else if(n<=m && count!=0 && count<=n){
res=res+con(n,count);
System.out.println((res)%(long)(Math.pow(10,9)+7));
return;
}
else if(n==m && count==0)
{
res=res+2;
System.out.println((res)%(long)(Math.pow(10,9)+7));
return;
}
}
res=res+con(n,count);
fun(n-m+1,m,count+1,res);
}
public static int con(int x,int y){
int a=fact(x);
int b=fact(y);
if(b==0)
b=1;
int c=fact(x-y);
if(c==0)
c=1;
int d=b*c;
return a/d;
}
public static int fact(int a){
if(a==0 || a==1)
return 1;
return a*fact(a-1);
}
}
"