Last Updated: 7 Mar, 2021
Binomial Coefficient Problem
Easy
Asked in companies
A Ninja was learning how to calculate the binomial coefficient. But, learning that alone won’t help the ninja since a lot of problems are required to be solved as homework. Since the ninja is old-fashioned and doesn’t know that a computer can do the same homework in a matter of a few seconds you will have to help with the problems.
You need to complete a function for the ninja that can calculate the binomial of a number where when given two integers 'N' and 'R', the program can calculate its respective binomial coefficient nCr. Since the answer may be very large, calculate the answer modulo 10^9 + 7.
For Example:
Input: 'N' = 5, 'R' = 2
Output: 10
The value of 5C2 is 10
After taking the modulo with 10^9 + 7 we get 10.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the 'T' test case are as follows.
The first line of each test contains an integer 'N' and an integer ‘R’, both separated by a space.
Output format:
For every ‘N’ and ‘R’, print its binomial coefficient nCr modulo 10^9 + 7.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
1 <= N <= 1000
1 <= R <= 800
Where ‘N’ and ‘R’ are the constants for calculating the binomial coefficient.
Time limit: 1 sec
Approaches
The key observation here is that we can the following fact that the value of C(n, k) can be recursively calculated using the following standard formula for Binomial Coefficients.
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
Steps:
- We check the base case of whether ‘N’ is greater than ‘R’, if no we return 0.
- First take a 2D ‘DP’ array ( C[i][j] ) which would be sized C[N + 1][R + 1].
- Now, calculate the value of the Binomial Coefficient in a bottoms-up manner.
- Now, for 'i' in ( 0 , ‘N’ + 1 ):
- For ‘j’ in ( 0 , min( ‘i’ , ‘R’ + 1 ) )
- If ‘j’ is 0 or equals ‘i’ then, ‘C[i][j]’ = 0.
- Else, ‘C[i][j]’ = (C[i - 1][j - 1] + C[i - 1][j]) mod 10^9 + 7.
- For ‘j’ in ( 0 , min( ‘i’ , ‘R’ + 1 ) )
- We finally return 'C[N][R]' mod 10^9 + 7.
C(n, k) = n! / (n-k)! * k! = [n * (n-1) *....* 1] / [ ( (n-k) * (n-k-1) * .... * 1) * ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]
i.e. , C(n, k) = C(n, n-k)
Thus, r can be changed to n-r if r > n-r
Steps:
- We check base case of whether ‘N’ is greater than ‘R’, if no we return 0.
- Now, we change ‘R’ to ‘N - R’ if ‘R’ > ‘N - R’ and create a variable ‘RES’ to store the answer.
- Now we basically check both C(N, R), C(N, N - R), and choose the smaller value
- While ‘R’ is not zero we iterate from 0 to ‘R’ - 1:
- In every iteration we update the answer as (ANS * (N - i) ) * inverseMod((i + 1) , 10^9 + 7) where i is the loop counter.
- So the answer will be equal to ((n / 1) * ((n - 1)/2)*…*((n - r + 1)/r) which is equal to nCr.
- We finally return ‘RES’ mod 10^9 + 7.