Today we are going to talk about how to compute nCr in the programming competitions.
1. Dynamic programming Approach :
From the high school mathematics we know a recursive method to calculate nCr i.e.
C(n,r) + C(n,r-1) = C(n+1,r)
This can also be written as
C(n,r) = C(n-1,r) + C(n-1,r-1)
It’s a very simple DP, as you can see nothing to be afraid of here.
Time complexity = O(n*r)
Space complexity = O(n*r)
2. Expand nCr
C(n,k) = n!/((n-k)!k!) [n(n-1)...(n-k+1)][(n-k)...(1)] = ------------------------------- [(n-k)...(1)][k(k-1)...(1)]
this can also be written as
C(n,k) = 1, if k = 0 = (n/k)*C(n-1, k-1), otherwise
3. Using Euler’s theorem and modular multiplicative inverse
Modular Multiplicative Inverse :
In modular arithmetic, the modular multiplicative inverse of an integer ‘a’ modulo ‘m’ is an integer ‘x’ such that
ax = 1 (mod m)
Euler’s theorem :
According to Euler’s theorem, if ‘a’ is coprime…
View original post 620 more words