Program written to calculate nCr value (C++)

Question

I have written below code to calculate nCr for n testCount values. It seems to work fine for my values but testcases of hacker earth fails, link of problem http://www.hackerearth.com/problem/golf/minimal-combinatorial/description/ can anybody tell me what are the potential fallacy in my logic

`#include <iostream>
 using namespace std;

 int main()
{
    int testCount; 
    int n , r;
    cin >> testCount;
    for (int i = 0 ; i < testCount ; i++)
    {

        long int a=1;
        long int b=1;
        long int c=1;
        cin >> n;
        cin >> r;
        for (int i = n ; i > 1 ; i--)
        {
             a = a * i;
        }
        for (int i = n-r; i >= 1 ; i--)
        {
            b=b*i;
        }
       for (int i=r;i >=1;i--)
       {
           c=c*i;
       }
       long int result=a/(b*c);
       cout << result<<"\n";
    }

    return 0;
}

` simplified numerator and denominator case

 `#include <iostream>
  using namespace std;

int main()
{
   int testCount; 
   int n , r;
   cin >> testCount;
  for (int i = 0 ; i < testCount ; i++)
  {

       long int numerator=1;
       long int denominator=1;
       cin >> n;
       cin >> r;
       for (int i = n ; i > r ; i--)
       {
          numerator = numerator * i;
       }
       for (int i = n-r; i >= 1 ; i--)
       {
           denominator=denominator*i;
       } 

       long int result=numerator/denominator;
       cout << result;
   }

    return 0;

} `

You may have overflow, you may simplify yourselfs common factor from numerator/denominator. — Jarod42, Oct 31 '14 at 19:32
Related to [which-is-better-way-to-calculate-ncr](http://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr) — Jarod42, Oct 31 '14 at 19:35
@Jarod42 I did that also , but it also fails . I should not have overflow as they have restricted the value to singed 64 bit int . The simplified version is in edit — Ajay, Oct 31 '14 at 19:36
the final result fits in an 64bit integer, but `b * c` may not. — Jarod42, Oct 31 '14 at 19:39
you have to take `r = max(r, n - r)` in your second sample to avoid some other possible overflow. — Jarod42, Oct 31 '14 at 19:42

score 2 · Accepted Answer · answered Oct 31 '14 at 19:46

Both of your code may overflow (even if result should fit in a 64 bit integer)

You may try:

std::uint64_t cnr(int n, int r)
{
    std::uint64_t ans = 1;
    r = std::min(r, n - r);

    for(int j = 1; j <= r; j++, n--) {
        // all following do: ans = (ans * n) / j;
        // but the 2 first cases do some simplifications
        // to reduce the possibility of overflow

        if (n % j == 0) {
            ans *= n / j; 
        } else if (ans % j == 0) {
            ans = (ans / j) * n;
        } else {
            ans = (ans * n) / j;
        }
    }
    return ans;
}

Program written to calculate nCr value (C++)

1 Answers1