1

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;

} `

5
  • 1
    You may have overflow, you may simplify yourselfs common factor from numerator/denominator.
    – Jarod42
    Oct 31, 2014 at 19:32
  • 1
    Related to which-is-better-way-to-calculate-ncr
    – Jarod42
    Oct 31, 2014 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, 2014 at 19:36
  • 1
    the final result fits in an 64bit integer, but b * c may not.
    – Jarod42
    Oct 31, 2014 at 19:39
  • 1
    you have to take r = max(r, n - r) in your second sample to avoid some other possible overflow.
    – Jarod42
    Oct 31, 2014 at 19:42

1 Answer 1

2

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;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.