Is there any other method to find ncr with good time complexity
#include
using namespace std;
#define ll long long
ll int C(ll int n,ll int k)
{
if(k==0 || k==n)
{
return 1;
}
return C(n-1,k-1)+C(n-1,k);
}
int main() {
// your code goes here
ll int T;
cin>>T;
while(T–)
{
ll int n,k;
cin>>n>>k;
cout<<C(n-1,k-1)<<endl;
}
return 0;
}
Why I am getting TLE
Hello Ankit, yes you can use bottom up method or memoize this. Here you are using purely recursive function and because of this it has exponential time complexity and that’s why it also gives TLE. So in order to avoid this use bottom-up dp or top-down dp (memoization) just introduce a 2-d dp array with all values initialised with -1 and then check for every dp[n][k] and also store the ans at the end. So I hope you know the idea of memoization and how to use it.
So I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks 
Happy Coding !!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.