CODEWITHSUNDEEP
c
Rahul Sonwanshi
Rahul Sonwanshi

Reputation: 105

Find number of possible triplets (including duplicates) of elements of Array in linear time?

I tried using the nCm function to find all combinations but for large numbers it fails

int fact(int num)
{
    if (num == 1 || num == 0)
        return 1;
    return num * fact(num-1);
}

int nCm(int num, int base)
{
    int result;
    return result = fact(num) / (fact(num - base)*fact(base));
}

where base = 3 and num can be anything so for large num it fails. I cannot use bigInteger library so please help

Upvotes: 1

Views: 332

Answers (1)

paddy
paddy

Reputation: 63481

If you consider that division for a moment, you'll see that the (n-b)! term is common to both numerator and denominator (i.e. they cancel out).

You just need to think of n! as:

n * (n-1) * (n-2) * ...  * (n-b+1) * (n-b)!

Now you can calculate the result without any division or large intermediate values (which could overflow), and you can also do it without recursion.

Upvotes: 1

Related Questions