Hey Ninjas! While solving data structure problems, you must have heard about the term binomial coefficients. If not, then you will be familiar with the binomial coefficients soon. Binomial coefficients are the number of chances to choose a group of items from among different items available without considering how they are arranged.
The binomial coefficient is also called nCr, where 'r' is the item from 'n' numbers of items. This blog will discuss the Binomial Coefficients with proper examples and working codes with their outputs.
Suppose there are 5 different types of fruits in a box, and we have to take 3 fruits from the box. Now, we have two inputs, 'n' and 'r', where 'n' is 5, and 'r' is 3.
We can find the binomial coefficient for the above problem statement.
Formulas
The formulas to find binomial coefficients are given below. Let's have a look.
First, we will see the mathematical formula to find the binomial coefficient.
nCr = n!/r! * (n-r)!
Note: n ≥ r ≥ 0 The next formula is given below.
C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
where C(n, 0) = C(n, n) = 1.
The reason behind this is
If 'r' = 0, we have to pick 0 or no items out of 'n' items, and there is only one way to pick it.
If 'r' = 'n', then we have to pick 'n' items out of 'n' items, and there is only one way to pick it.
Sample Example
Let's first see the example using the mathematical formula.
Hence, the number of chances to choose all 3 fruits from 5 fruits is 10.
Brute Force Approach
As we have seen in the formula, there is one method which can be done by using the Recursion. So, we will use the recursion to find the binomial coefficient of the given problem statement.
Algorithm
We will understand the algorithm stepwise.
Initialize two variables in the main function, ‘n’ and ‘r’ and call the ‘BinomialCoeff’ function.
Inside the ‘BinomialCoeff’ function, return 1 if either ‘r=0’ or ‘r=n’, as discussed in the Formulas section.
Return 0 if the ‘r’ is greater than n (r>n).
Now use the recursion function for (n-1) and (r-1), and store the result in ‘res1’.
Again, use the recursion function for (n-1) and (r), and store the result in ‘res2’.
Return the sum of ‘res1’ and ‘res2’ and print the sum as output.
Dry Run
Now we will see a dry run using the recursion formula with a pictorial representation. The formula we are going to use is as follows:
C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
where, n = 5, and r = 3
In the above diagram, our task is to simplify or use the recursion process until we reach the endpoint, which is 1. The values will become 1 by following the rule (C(n, 0) = C(n, n) = 1) as discussed above.
Implementation in Java
public class CodingNinjas {
int BinomialCoeff(int n, int r) {
// Base condition for recursive function when r=0
if (r == 0) {
return 1;
}
// Base condition for recursive function when r=n
if(r == n) {
return 1;
}
if (r > n) {
return 0;
}
// Here, we are using Recursion
int res1 = BinomialCoeff(n - 1, r - 1);
int res2 = BinomialCoeff(n - 1, r);
return res1 + res2;
}
public static void main(String[] args) {
CodingNinjas codingninjas = new CodingNinjas();
int n = 5;
int r = 3;
int result = codingninjas.BinomialCoeff(n, r);
System.out.println("The result is " + result);
}
}
Output:
Implementation in C++
#include <iostream>
using namespace std;
int BinomialCoeff(int n, int r) {
// Base condition for recursive function when r=0
if (r == 0) {
return 1;
}
// Base condition for recursive function when r=n
if(r == n) {
return 1;
}
if (r > n) {
return 0;
}
// Here, we are using Recursion
int res1 = BinomialCoeff(n - 1, r - 1);
int res2 = BinomialCoeff(n - 1, r);
return res1 + res2;
}
int main() {
int n = 5;
int r = 3;
int result = BinomialCoeff(n, r);
cout<< "The result is " << result;
}
Output:
Implementation in Python
def BinomialCoeff(n, r):
# Base condition for recursive function when r=0
if r == 0:
return 1;
# Base condition for recursive function when r=n
if r == n:
return 1;
if r > n:
return 0;
# Here, we are using Recursion
res1 = BinomialCoeff(n - 1, r - 1)
res2 = BinomialCoeff(n - 1, r)
return res1 + res2;
n = 5;
r = 3;
result = BinomialCoeff(n, r)
print ("The result is", result);
Output:
Time Complexity
The above approach's time complexity is O(2 ^ (n / 2)), as the recursion function calls itself 2 times in every execution. The recursion function will stop once the value of r becomes 0. The reason behind the n/2 is that we need at least n/2 steps until r reaches 1 or n goes n/2 in any recursive call.
Space Complexity
The space complexity for the above approach is O(n / 2), as the internal stack is used in recursion, and the max height can be 'r', i.e., 'n / 2'.
When calling a recursive function, the internal stack is overhead. The reason for the overhead is we are going through the complete process two times. By using a non-recursive method, we can get rid of this overhead.
We will use the mathematical formula for the optimal approach. Let's recall the formula we discussed earlier in this blog.
Algorithm
We will understand the algorithm stepwise. Let's go.
Initialize two variables in the main function, ‘n’ and ‘r’ and call the ‘BinomialCoeff’ function.
Initialize a local variable with the name ‘result’ and assign it to value 1.
Now, if ‘r’ is greater than ‘n - r’, then update the value of ‘r’ to ‘n - r’.
Start a for loop from 0 to less than ‘r’ with pre-increment.
Inside the loop, multiply the result by ’n - i’ and update the result.
Next, divide the result by ‘i + 1’ and update the result.
Return and print the result as the output.
Flow Chart
Dry Run
Now, let's understand the above flowchart using a dry run. We will take the same example as above, where n = 5 and r = 3.
In the main method, the program will call the BinomialCoeff function after assigning the values to the 'n' and 'r'.
A result variable with the value 1 will be assigned after entering the BinomialCoeff function.
The first 'if condition' says to check whether 3 is greater than 5. This will return 'false' means it will come out from the 'if condition'.
Next, it comes to the second 'if condition', which says to compare whether 3 is greater than 5-3, which is true. Then it will update the value of 'r' to 5-3. So, the new value of 'r' is 2.
Now it will enter in a 'for loop'. It will check the condition i < r, where 'i' = 0 and 'r' = 2. The condition is true, so it will enter the loop.
when i = 0: result = 1 * (5 - 0) = 5 result = 5 / (0 + 1) = 5
After this, it will again check the condition of the 'for loop'. Now, the value of i is updated to 1, and 'r' is 2. The condition (i < r) is still true, so it will enter the loop.
when i = 1: result = 5 * (5 - 1) = 20 result = 20 / (1 + 1) = 10
After this, it will again check the condition of the 'for loop'. Now, the value of i is updated to 2, and 'r' is 2. The condition (i < r) is now false, so it will come out of the loop.
Now it will return the value of the result, which is 10 and print it.
Implementation in Java
public class CodingNinjas {
int BinomialCoeff(int n, int r) {
int result = 1;
if (r > n) {
return 0;
}
if (r > n - r) {
r = n - r;
}
// Applying Mathematical Formula
for (int i = 0; i < r; i++) {
result = result * (n - i);
result = result / (i + 1);
}
return result;
}
// Main method
public static void main(String[] args) {
CodingNinjas codingNinjas = new CodingNinjas();
// Inputs
int n = 5;
int r = 3;
// Method calling
int result = codingNinjas.BinomialCoeff(n, r);
// Printing result
System.out.println("The result is " + result);
}
}
Output:
Implementation in C++
#include <iostream>
using namespace std;
int BinomialCoeff(int n, int r) {
int result = 1;
if (r > n) {
return 0;
}
if (r > n - r) {
r = n - r;
}
// Applying Mathematical Formula
for (int i = 0; i < r; i++) {
result = result * (n - i);
result = result / (i + 1);
}
return result;
}
int main() {
int n = 5;
int r = 3;
// Method calling
int result = BinomialCoeff(n, r);
// Printing result
cout<<"The result is " << result;
}
Output:
Implementation in Python
def BinomialCoeff(n, r):
result = 1;
if (r > n):
return 0;
if (r > n - r):
r = n - r;
#Applying Mathematical Formula
for i in range(0, r):
result = result * (n - i);
result = result / (i + 1);
return result;
n = 5;
r = 3;
# Method calling
result = BinomialCoeff(n, r);
# Printing result
print("The result is", int(result))
Output:
Time Complexity
The time complexity for the optimal approach is O(K). Here, ‘K’ is the number of iterations of the for loop.
Space Complexity
The space complexity for the optimal approach is O(1), as we have not used any extra space.
Binomial coefficients are the number of ways to select 'r' items from 'n' different items without considering the order of arrangement of these items. It is represented as C(n, r).
What is the formula to calculate Binomial Coefficient?
The binomial coefficient can be calculated using two formulas that are C(n, r) = C(n-1, r-1) + C(n-1, r) and C(n, r) = n! / r! (n-r)!
Where is the binomial combination used?
Combinations are used when we have to select a group of something without considering the order in which we select them or their arrangement.
What are the ways to solve the binomial coefficients?
You can solve the binomial problem in different ways, like recursion, memoization technique (an extension to the recursive approach), and the Pascal triangle rule.
What do you mean by Pascal Triangle?
The Pascal triangle is a triangle-shaped collection of binomial coefficients that appears in algebra, combinatorics, and probability theory.
Conclusion
This article discusses the topic of Binomial Coefficients. In detail, we have seen the problem statement, examples, brute force approach, and optimal approach, both with algorithm, implementation, time and space complexity.
We hope this blog has helped you enhance your knowledge of Binomial Coefficients. If you want to learn more, then check out our articles.
But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
39+ registered 