CODEWITHSUNDEEP
javaoverflow
Rohit Banga
Rohit Banga

Reputation: 18926

how to find n choose r without overflow

I need to find the value of n choose r- the number of ways of selecting r objects out of n.

if i first find the numerator then the denominator. i get an exception.

i am using java.

how to do it for example for 44 choose 42

Upvotes: 3

Views: 699

Answers (1)

user319799
user319799

Reputation:

You can use the fact that NcR is equal to Nc(N-R). The formula is:

 N * (N - 1) * ... * (N - R + 1)
---------------------------------
         1 * 2 * ... * R

You can observe that product of K consecutive numbers is always divisible by K. So, the loop would look like

  • multiply two numbers from nominator
  • divide by 2
  • multiply by the 3rd number from nominator
  • divide by 3
  • ...
  • multiply by the last number from the nominator
  • divide by R

Alternatively, just use java.math.BigInteger.

Upvotes: 4

Related Questions