TO FIND nCr OF TWO NUMBERS N AND R BY GCD METHOD

#1

CAN U PLEASE EXPLAIN THIS CODE SNIPPET TO FIND nCr
I FOUND IT ON GEEKS FOR GEEKS

PRINT nCr FUNCTION PRINTS nCr

void printNcR(int n, int r)
{

// p holds the value of n*(n-1)*(n-2)..., 
// k holds the value of r*(r-1)... 
long long p = 1, k = 1; 

// C(n, r) == C(n, n-r), 
// choosing the smaller value 
if (n - r < r) 
    r = n - r; 

if (r != 0) { 
    while (r) { 
        p *= n; 
        k *= r; 

        // gcd of p, k 
        long long m = __gcd(p, k); 

        // dividing by gcd, to simplify product 
        // division by their gcd saves from the overflow 
        p /= m; 
        k /= m; 

        n--; 
        r--; 
    } 

    // k should be simplified to 1 
    // as C(n, r) is a natural number 
    // (denominator should be 1 ) . 
} 

else
    p = 1; 

// if our approach is correct p = ans and k =1 
cout << p << endl;

}

#2

Hi Anshuman, so for finding nCr we use factorials and then calculate the answer. But as you know, the value of factorials can be quite large and the answer may overflow. So to overcome this problem, this code is dividing the numerator and denominator by their GCD or HCF at every step. In layman terms, we eliminate the common factors as we might do when performing division by hand. For example, 8/6 can be reduced to 4/3 by dividing both 8 and 6 by 2, ie their HCF. Since nCr is always a whole number, in the end k(denominator in this case) is sure to be 1 and p(numerator) will give us the answer.

#3

You know
C(n,r)=n!/r!(n-r)!
or
C(n,r)=nn-1n-2n-3…/rr-1r-2…
As in the code we are calculating it like (n/r)(n-1/r-1)… so on.Here n is might not be a multiple of r, also we cannot store nn-1n-2*n-3… in any integer or long (it will most probably lead to overflow), so in the code we are finding gcd of p and k and are dividing both by their gcd so as to prevent overlow.

#4

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.