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
I think so. Lol!
2 Likes
Have u did?
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