Detecting Overflow In nCr Function

Question

I have two functions here that together compute the nCr:

int factorial(int n) {
int c;
int result = 1;

 for (c = 1; c <= n; c++)
 {
  result = result*c;

 }

return result;
}




int nCr(int n, int r) {
int result;

 result = factorial(n)/(factorial(r)*factorial(n-r));

 return result;
}

I am having trouble with an error check I need to implement. As n gets larger, I won't have the ability to computer n! and this error check has to exist in both nCr and factorial. They both must detect this overflow.

Currently, when I enter a number that is too large for computation, I get a floating type error returned from the command line.

I am having trouble accounting for this overflow check. Any help would be much appreciated, thanks.

Answer 1

In your code, the maximum value is always factorial(n),
so you only need to check that n! isn't bigger than 2.147.483.647 (max int value).

Please note that the stored max value can be different based on the size of the int type in memory (different machines can specify different sizes).

However, the last bit in int type variables is reserved for storing the sign (+ or -), thus the max value can be half of 65.535 and 4.294.967.295 i.e. 32.767 and 2.147.483.647 for int types.

SIZE_OF_INT(bits)    MAX VALUE(UNSIGNED)     MAX_VALUE(SIGNED)
---------------------------------------------------------------
16                   65.535                  32.767
32                   4.294.967.295           2.147.483.647

The value of 13! can go beyond the max value of the int type (in 32 bit).

12! = 479.001.600 and
13! = 6.227.020.800

So, you need to check in nCr(int n, int r) that the max value of n is always less than 13 (i.e. n<=12) and r<=n. And in factorial(int n): n<=12.

Answer 2

A better way of calculating binomial coefficients

typedef unsigned long long ull;

ull nCr(int n, int r) {
    ull res = 1;
    if (r > n - r) r = n - r;
    for (int i = 0; i < r; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}