CODEWITHSUNDEEP
ccombinationsncr
Kasun Jalitha
Kasun Jalitha

Reputation: 25

How can I fix this Combinations calculating(nCr) program?

I have created this simple program using c to calculate combinations. But whenever I enter large value like 20,30,40.. for variable 'n' and for 'r' program output is not true. But this program works fine with small numbers like 5,7,10... How can i fix this problem to find combinations even input big numbers for n and r ?

Also I wanna use nCr = n-1Cr + n-1Cr-1 rule in this program and I am using C language

#include <stdio.h>

int fact(int i){             

    if(i <= 1){
        return 1;       
    }
    return i * fact(i-1);
} 


int nCr(int n,int r){

    int nCr;

    if(r == 0 || n == r){
        nCr = 1;
    }else{

        nCr = (fact(n-1)/(fact(r) * fact(n-1-r))) + (fact(n-1)/(fact(r-1) * fact(n-r)));

    }
    return nCr;
}

int main(){

    int n,r;

    printf("Enter n : ");
    scanf("%d",&n);
    printf("Enter r : ");
    scanf("%d",&r);

    printf("nCr value : %d\n",nCr(n,r));
    return 0;
}

Thank you so much for your answers.

Upvotes: 0

Views: 508

Answers (2)

chux
chux

Reputation: 154243

How can i fix this problem to find combinations even input big numbers for n and r ?

  • Use a wider integer type. 32-bit int good only to fact(12).

  • Compute nCr(int n,int r) without using fact(). Form the product/quotient in steps.

  • Use floating point math and tolerate inexactness.

Let us go for door # 2. The idea to use * and / in each step.

Example, with 52 cards there are 2,598,960 different power hands.

uintmax_t nCr(unsigned n, unsigned r) {
  uintmax_t y = 1;
  if (r <= n) {
    if (n - r + r < r + r) {
      r = n - r;
    }
    for (unsigned i = 1; i <= r; i++) {
      y = y * (n - r + i) / i;
    }
  }
  return y;
}

int main(void) {
  printf("%ju\n", nCr(52, 5));  // 2598960
  return 0;
}

Upvotes: 0

Dheeraj Yandrapu
Dheeraj Yandrapu

Reputation: 83

For large numbers use long long int instead of int. Try this instead:

#include <stdio.h>

long long int fact(long long int i){             

if(i <= 1){
    return 1;       
}
   return i * fact(i-1);
} 


long long int nCr(long long int n,long long int r){

long long int nCr;

if(r == 0 || n == r){
    nCr = 1;
}else{

    nCr = (fact(n-1)/(fact(r) * fact(n-1-r))) + (fact(n-1)/(fact(r-1) * fact(n-r)));

}
    return nCr;
}

int main(){

    long long int n,r;

    printf("Enter n : ");
    scanf("%lld",&n);
    printf("Enter r : ");
    scanf("%lld",&r);

    printf("nCr value : %lld\n",nCr(n,r));
    return 0;
}

Upvotes: 0

Related Questions