Question

Write a c++ program where it computes n choose k by using the formula: n(n-1)(n-2)...(n-k+1)/k!. But do not use algorithms where you can use only use integer arithmetic. How is this better than writing a program that uses the formula n!/k!(n-k)!

Answer 1

C++ CODE:

#include<iostream>

using namespace std;

#define ll long long

ll factorial(ll n)

{

                if(n==0||n==1) return 1;

                else return n*factorial(n-1);

}

ll nCr(ll n,ll k)

{

                ll prod=1;

                for(int i = n;i>=n-k+1;i--)

                {

                                prod*=i;

                }

                prod/=factorial(k);

}

int main()

{

                ll n,k;

                cout<<"Enter n, k"<<endl;

                cin>>n>>k;

                cout<<n<<"C"<<k<<" = "<<nCr(n,k)<<endl;

                return 0;

}

OUTPUT:

Enter n, k 10 5 10C5 252 Process exited after 1.745 seconds with return value e Press any key to continue .. .

BENEFIT OVER METHOD USING n!/k!(n-k)!

Computation of factorial(n) itself takes linear time in n.So, the number of computations are significantly reduced when we use n(n-1)(n-2)...(n-k+1)/k! to compute nCk over n!/k!(n-k)! because we have to calculate only k! while in the second method we had to calculate 3 factorials.