CODEWITHSUNDEEP
ccombinations
flexwang
flexwang

Reputation: 653

How can I get a combination number without exceeding

I want to write a function to get a combination_n_k. And here is what I did:

int com(int n, int k)
{
    int result = 1;

    for( int i=n; i>(n-k); i--)
        result *= i;

    for( int i=k; i>1; i--)
        result /= i;

    return result;
}

This works fine for small number, but when it turn to big number, the result just exceed the max of int. Is there any better way to do this?

Upvotes: 0

Views: 81

Answers (1)

user529758
user529758

Reputation:

You can get to a slightly higher bound by using unsigned long long and a bit more clever algorithm:

unsigned long long n = /* n */, k = /* k */;

unsigned long long p = 1; /* accumulates the product */
unsigned long long m = k < n - k ? k : n - k; /* min(k, n - k) */
k = m;

unsigned long long i = n - k + 1;
unsigned long long j = 1;

while (m-- > 0) {
    p = p * i++ / j++;
}

If this is still not enough, then you will have to use a bigint library.

Upvotes: 1

Related Questions