## Sunday, August 23, 2009

### Calculate nCr with out having overflow when it is guaranteed that the final result will not overflow:

From pascal's triangular relation, we get,
nCr = n-1Cr + n-1Cr-1

Using this recursive formula directly will lead the program to exceed the time limit, as this may calculate the same value for many times which is un-necessary and we can remove this part by saving the states which means by using dynamic programming concepts.

In this formulation, one thing is to be noted that n and r keep decreasing, and sometimes is is possible that n becomes smaller than r. So considering these cases we get our base conditions for the recursive formula.

We know,
nCn = 1
nC1 = n
nC0 = 1
and
nCr = n-1Cr + n-1Cr-1

So, we can build the recursive function as follows:
`function nCr(n, r):    if n == r:        return 1    if r == 1:        return n    if r == 0:        return 1    return nCr(n-1, r) + nCr(n-1, r-1)`

Now, to reduce recursive steps, we maintain a table for saving the values of nCr of intermediate steps. So, when we face a sub-problem which is already solved, we can look up its value from the pre-calculation table.
`table dp[N][R]function nCr(n, r):    if n == r:        dp[n][r] = 1    if r == 1:        dp[n][r] = n    if r == 0:        dp[n][r] = 1    if dp[n][r] is not yet calculated:        dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1)    return dp[n][r]`

Here is a sample code written in C++ which demonstrates the idea. (It is assumed that MAX N is 65 and N >= R).

`#include <stdio.h>#define i64 unsigned long longi64 dp;i64 nCr(int n, int r){    if(n==r) return dp[n][r] = 1;    if(r==0) return dp[n][r] = 1;    if(r==1) return dp[n][r] = (i64)n;    if(dp[n][r]) return dp[n][r];    return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}int main(){    int n, r;    while(scanf("%d %d",&n,&r)==2)    {        r = (r<n-r)? r : n-r;        printf("%llu\n",nCr(n,r));    }    return 0;}`

Plain and simple!!!

1. say a case if n<=2^64 && r<=64

2. @Anonymous, give me infinite memory with infinite time, all your problems are solved.

Anyways, there's another technique for your situation. It is simple as well. We can always write nCr in the form denom/num, we can do this by successively multiplying and dividing.

3. THANKS MAN! I NEEDED THIS!

4. Hey guys I wrote a post here for more details
supercool276.blogspot.in