Binomial Coefficient Problem

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
HSBCAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
5 2     
3 2        
3 1
Sample Output 1:
10
3
3
Explanation For Sample Input 1:
For first test case, the Binomial coefficient (5C2) is 10, which after performing modulo with 10^9 + 7 is also 10.

For second test case, the Binomial coefficient (3C2) is 3, which after performing modulo with 10^9 + 7 is also 3.

For third test case, the Binomial coefficient (3C1) is 3, which after performing modulo with 10^9 + 7 is also 3.
Sample Input 2:
2
2 4
4 2
Sample Output 2:
0
6
Explanation For Sample Input 2:
For first test case, the Binomial coefficient (2C4) is not possible as N < R.

For second test case, the Binomial coefficient (4C2) is 6, which after performing modulo with 10^9 + 7 is also 6.
Hint

Try to divide big problems into small sub-problems.

Approaches (2)
Divide and Conquer

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:

  1. We check the base case of whether ‘N’ is greater than ‘R’, if no we return 0.
  2. First take a 2D ‘DP’ array ( C[i][j] ) which would be sized C[N + 1][R + 1].
  3. Now, calculate the value of the Binomial Coefficient in a bottoms-up manner.
  4. 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.
  5. We finally return 'C[N][R]' mod 10^9 + 7.
Time Complexity

O(N * R) , Where ‘N’ and ‘R’ are the constants given for calculating the binomial coefficients.

 

Now, since we are iterating through R + 1 times for every number in the range (0, N + 1). So the time complexity grows O(N * R).

Space Complexity

O(N * R) , Where ‘N’ and ‘R’ are the constants given for calculating the binomial coefficients.

 

Since we are using a 2D array C[i][j] of size N * R, therefore, we need O(N * R) space.

Code Solution
(100% EXP penalty)
Binomial Coefficient Problem
Full screen
Console