CODEWITHSUNDEEP
c
CurryFlurry
CurryFlurry

Reputation: 25

Combination Problems with big numbers (3, 123) in C

a real newbie to c here.. been learning it for 6 weeks now so idk a lot of stuff yet (we just learned nested functions, i'm still making newbie mistakes everywhere..)

I got a hw about combination with 3 parts, and wrote my codes that worked for the first two (like (3,10)) but I found that the third part was (3, 123) and of course my codes couldn't handle it without overflowing

here's the code that I wrote:

#include<stdio.h>

long long int factorial(int x)   
{   int y; 
    long long int z=1;
    for (y=1; y<=x; y++)
    {z*=y;}
    return z;
}

long long int combination(int b, int c) 
{long long int a, d, e; 
a= factorial(c);
d= factorial(c-b) * factorial(b);
e= a/d;
return e;
}

int main()
{   int draws, total;
    scanf("%d %d", &draws, &total);
    printf("%lld", combination(draws, total));
    return 0;
}

works right upto long long int ofc but nothing like 123! I spent like 2-3 hours digging around the internet and found some stuff like itoa (no idea what that is.. never heard of it), array, string etc but that just helps store the value and doesn't help with the actual calculation.. and something called GMP? tried putting #include< gmp.h> and it said that it cant find it. if it gives that error then im pretty sure i cant use it for my hw. tbh idk y our teacher gave us this considering he didnt tell us how to solve these kinds of huge number overflow issue.. lol. thank you so much for the help.

Upvotes: 1

Views: 69

Answers (1)

rcgldr
rcgldr

Reputation: 28826

The parameters are backwards for the normal use of combination function. For combinations of n things taken k at a time, the syntax is comb(n,k). To reduce the size of the numbers involved:

c = max(k, n-k)
d = n-c
comb(n,k) = (n)(n-1)(n-2)...(n+1-c)/(d!)

examples:

comb(6,2)
c = max(2, 6-2) = 4
d = 6-4 = 2
comb(6,2) = (6·5)/(2·1) = 15

comb(123,3)
c = max(3, 123-3) = 120
d = n-c = 3
comb(123,3) = (123·122·121)/(3·2·1) = 302621

Upvotes: 5

Related Questions