How to calculate nCr values efficiently?

I tried using the formula nCr/nCr-1=n-r+1/r but in python the value is stored in scientific notation and the value changes if i convert it to an integer. Is there any way to do this without changing the value in python? (for large values of n)

2 Likes

for binomial fever?? @dormordo …LOL

2 Likes

I think so. Lol! :stuck_out_tongue:

2 Likes

Have u did? :slight_smile: :slight_smile:

I guess, this can help- https://www.geeksforgeeks.org/queries-of-ncrp-in-o1-time-complexity/

3 Likes

Im not in division 1 so why bother solving binomial fever lol

Thanks this really helped

Use Lucas Theorem for bigger value of N. If you have a modulo present to shorten your answer, then maybe try to calculate all factorials%M beforehand or use best known algorithm to calculate nCr%M.

To speed things up, you may try to use

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

its a fast way to obtain ncr values, but incase you have to find all values from 0-n, you may use identities to shorten your equation.
Like:-
nC0+nC1+nC2+. . . +nCn = 2^n
and other combinational binomial equations.

Good luck
1 Like

because the question is intresting one :slight_smile: