hi, anyone know how to modify this coding ( combination ncr) ? because if i put N=400 k=3 . the progam wouldn't calculated.tq:)

Question

#include <stdio.h>
int fact(int);

int main(void)
{
int N, k, p;

printf("Enter the values of N and k: ");
scanf("%d %d", &N, &k);

p = fact(N)/(fact(k)*fact(N-k));
printf("%d", p);
return 0;

}

int fact(int x)
{ int prod = 1, i;

for (i=x; i>1; i--)
prod = prod*i;

return prod;
}

Answer 1

Show your attempt and you'll get the help you need.

Answer 2

Minho 🇰🇷 no worries🤗

Answer 3

hidaya a cheap fix would be to use unsigned long int instead of int
If your sizeof(unsigned long) is 8 bytes then your maximum number is 2^64 that is around 1.8*10^19
20! = 2.4*10^18 is your max

I don't know how to arrive at 400! because I never needed to, but here's some useful informations:
https://stackoverflow.com/questions/2640625/store-and-work-with-big-numbers-in-c

Answer 4

Minho 🇰🇷 his function is doing the same job of yours. And the void in main is fine: https://stackoverflow.com/questions/12225171/difference-between-int-main-and-int-mainvoid

hidaya the problem is that 400! is too big to be stored by an int variable.

Supposing your sizeof(int) is 4 byte, the numbers you can store range from -2^(2*8) and +2^(2*8) so the biggest number would be 65536
9! = 362880

edit: it actually is 2^31 not 2^16, I am sorry

Answer 5

Davide sorry.. I didn't notice properly.. Thanks!!

Answer 6

When k is small you can calculate just the factorial(N)/factorial(N-k) as product of N-k+1, N-k+2,..., N to avoid the overflow. If k is close to N you can do the same with factorial(N) / factorial(k).

Also if you know an upper bound on your answer, you can take a prime larger than this bound and do calculations modulo this prime.

Alternatively you can use the recurrence property: binomial(N, k) = binomial(N-1,k)+binomial(N-1,k-1). Just save the intermediate results to avoid recalculating them.

If your answer gets larger than 2^128 (__uint128_t in gcc) than you need to use multiple precision arithmetics libraries (such as gmp in c), or switch to python which uses them by default.

Answer 7

Davide already.

Answer 8

Davide oh i see. so how can i modify the code ? to make the N=400 can run the program ? .

Answer 9

So your equation is basically this, p = N! / k! * (N-k)!, you can say then that k! * p = N!/(N-k)!, what in case of N=400 and k = 3, N!/(N-k)!, will be the same thing that write 400*399*398. So your code actually doesn't need to calculate this monstrous number. Which is very fortunate! To solve you make a variable i, create another one as well, like j store the value of N on j, then you open a for loop (i=1; i < k; i++), then inside the for loop multiply j by N-i, and store this value on j, like this, j = j *(N-i); , return j; and divide it by k! on main code, and finally store it on p. I think that it will do the job.