Computing the binomial coefficient in C

Question

I found the following code for computing nCr, but don't understand the logic behind it. Why does this code work?

long long combi(int n,int k)
{
    long long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

Answer 1

that's a clever code!

In general it aims to calculate the following formula:

ans = n! / (k!)(n-k)!

It is equal to:

ans = n(n-1)(n-2) ... (n-k)...1 / k(k-1)...1 * (n-k)(n-k-1) ... 1

And after obvious cancellation:

ans = n(n-1)(n-2)..(n-k+1) / k!

Now notice that nominator and denominator have the same number of elements (k element)

So the calculation of ans will be like the following:

ans  = 1 // initially
ans *= n/1
ans *= (n-1)/2
ans *= (n-2)/3
.
.
.
ans *=  (n-k+1)/k

take a look again at the code and you notice that:

1. ans is being multiplied by n at each iteration
2. n is reduced by 1 at each iteration (n--)
3. ans is divided by j at each iteration

This is exactly what is done by the posted code, Now let's see the meanings of different conditions in the loop, with nominator starting from n and denominator from 1 to k, so variable j is assigned to denominator right?

1) if(n%j==0)

at each step if n/j is (computable) So we calculate it first here than multiply to the whole ans, this practice keeps the result at its smallest possible value.

2) else if(ans%j==0)

at each step if we couldn't calculate n/j but actually can calculate ans/j so that's not bad to say :

ans /= j; //first we divide
ans *= n; //then we multiply

This is always keeping our overall output as small as possible, right?

3) last condition

at each step, if we couldn't compute neither n/j nor ans/j in this case we are not lucky enough to divide first then multiply (hence keeping the result small). But well we need to carry on even-though we are left with only one choice which is

ans *= n; // multiply first
ans /= j; // then divide

ET VOILA!

Example consider the case 3C7 we know that the answer is 7!/ 3!*4! hence : ans = 7*6*5 / 1*2*3

let's see what happen at each iteration:

//1 
ans = 1

//2 
n = 7
j = 1
ans = ans * n/j 
first compute 7/1 = 7
then multiply to ans
ans = 1*7
ans = 7

//3
n = 6
j = 2
ans = ans* n/j

evaluate n/j = 6/2 (can be divided)
         n/j = 3
ans = ans *(n/j)
    = 7 * 3
    = 21

// 4
n = 5
j = 3

ans = ans * n/j
evaluate n/j = 5/3 oppsss!! (first if)
evaluate ans/j = 21/3 = 7 YES (second if)

ans = (ans/j)*n
    = 7*5
    = 35

// end iterations

Note that in last iteration if we calculate straight forward we would say:

ans = ans*n/j
    = 21 * 5 / 3
    = 105 / 3
    = 34 

yes it does find right result but meanwhile the value flies up to 105 before getting back to 35. Now imagine calculating real large numbers?!

Conclusion This code is computing carefully the binomial coefficients trying to keep the output as small as possible at each step of calculation, it does that by checking if it is possible to divide (int) then execute, hence it is capable of calculating some very big kCn that the straightforward coding cannot handle (OverFlow may occur)

Answer 2

To answer the question in part, consider the fact that the entries of n choose k constitute Pascal's triangle. As Pascal's triangle is symmetric, it is sufficient to move the argument k into the left half, which is done with the

k=k>n-k?n-k:k;

statement; see the definition of C's conditional operator.

Furthermore, the result ans is initialized in the beginning to contain 1, which is the first entry of every row in Pascal's triangle, which means that initially, ans is in fact n choose j.