Given two integers n and r, the task is to find Binomial coefficients C(n, k) or nCr.
Binomial coefficients C(n, k) are the number of ways to select a set of elements from different elements without taking into account the order of arrangement of these elements (i.e., the number of unordered sets).
These are also called nCr representing that we have to choose "r" items from "n" distinct items.
Mathematically it is defined as - C(n,k) = n! / ((n-k)! * k!)
Input: n = 5 and k = 2
Output: 10
Input: n = 10 and k = 2
Output: 45
Solutions
Method 1: Calculate - nCr % p
The value of nCr%p is generally needed for large values of n when nCr cannot fit in a variable, and causes overflow.
If we take mod of a number by Prime the result is generally spaced in comparison to mod the number by non-prime, that is why primes are generally used for mod.
10^9+7 is the first 10-digit prime number and fits in int data type as well.
Complexity
The time complexity of this solution is O(2^n).
In addition, O(2^n) auxiliary space was used by the recursion stack.
Method 2: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" and "k" changes, so we can store and reuse the result of a function(..n, k..) call using a "n+1 * k+1" 2-D array.
The 2-D array will store a particular state (n, k) if we get it the first time.
Now, if we come across the same state (n, k) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n * k).
In addition, O(n * k) auxiliary space was used by the table.
Method 3: Recursion
The value of C(n, k) can be recursively calculated using the following standard formula for Binomial Coefficients.
C(n, r) = C(n-1, r-1) + C(n-1, r)
Complexity
The time complexity of this solution is O(2^n).
In addition, O(2^n) auxiliary space was used by the recursion stack.