The binomial coefficient \binom{n}{r} is the number of ways of picking r outcomes from n possibilities. The value of the binomial coefficient for n and r, where 0 <= r <= n is given by:
Recursive Approach to calculate Binomial Coefficient
Let’s calculate the value of C(n, r) by using the recurrence relation:
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}Optimal Substructure
C(n, r) = C(n-1, r-1) + C(n-1, r), where 0 < r <= n Also, C(n, n) = 0 & C(n, 0) = 0, for any n >= 0
Recursive Code
//
// main.cpp
// Binomial Coefficient (Recursive)
//
// Created by Himanshu on 01/04/22.
//
#include <iostream>
using namespace std;
// Calculate Binomial Coefficient C(n, r)
int calculateBinomialCoeff (int n, int r)
{
// Base Cases
if (r > n) {
return 0;
}
if (r == 0 || r == n) {
return 1;
}
// Recursion
return calculateBinomialCoeff(n - 1, r - 1)
+ calculateBinomialCoeff(n - 1, r);
}
int main () {
int n = 8, r = 2;
cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
return 0;
}
Output
C(8, 2) is 28
Time complexity: O(2n)
Understanding the problem in this approach
Here, certain subproblems are recomputed. Let’s see how,
Recomputations can be avoided by exploiting optimal substructure and overlapping subproblems property and using a Dynamic Programming solution.
Dynamic Programming Approach
We could create a 2d array, C[n][r] in bottom up manner, such that
C[i][j] = C[i-1][j-1] + C[i-1][j]
where C[i][j] = {i \choose j}
Code Implementation (Dynamic Programming Approach)
//
// main.cpp
// Binomial Coefficient (Dynamic Programming)
//
// Created by Himanshu on 31/03/22.
//
#include <iostream>
using namespace std;
typedef long long ll;
// Calculate Binomial Coefficient C(n, r)
ll calculateBinomialCoeff (int n, int r) {
ll C[n+1][r+1];
for (int i=0; i<=n; i++) {
for (int j=0; j<=i && j<=r; j++) {
// first and last binomial coefficients are
// always 1
if (j == 0 || j == i) {
C[i][j] = 1;
} else {
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
}
return C[n][r];
}
int main() {
int n = 8, r = 2;
cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
return 0;
}
Output
C(8, 2) is 28
Time complexity: O(n*r)
Space complexity: O(n*r)
Also read:
Optimal space and time complexity approach
We know that,
C(n, r) = \frac{n!}{(r!)(n-r!)}
Simplifying C(n, r) = \frac{n!}{(r!)(n-r!)} = \frac{n * (n-1) *....* 1}{( r * (r-1) * .... * 1 ) * ((n-r) * (n-r-1) * .... * 1)} Cancelling factors between numerator and denominator, we get: = \frac{n * (n-1) *....* (n-r+1)}{( r * (r-1) * .... * 1 ) } Also, C(n, r) = C(n, n-r). So we would use C(n, min(r, n-r)) to calculate binomial coefficient
Code Implementation
//
// main.cpp
// Binomial Coefficient (Efficient)
//
// Created by Himanshu on 01/04/22.
//
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
// Calculate Binomial Coefficient C(n, r)
ll calculateBinomialCoeff (int n, int r) {
ll binomialCoeff = 1;
if (n < r) {
return -1;
}
r = min(r, n-r);
for (ll i=n; i>n-r; i--) {
binomialCoeff = binomialCoeff*i;
binomialCoeff = binomialCoeff/(n-i+1);
}
return binomialCoeff;
}
int main() {
int n = 8, r = 2;
cout<<"C("<<n<<", "<<r<<") is "<<calculateBinomialCoeff (n, r)<<endl;
return 0;
}
Output
C(8, 2) is 28
Time complexity: O(r)
Space complexity: O(1)
One thought on “How to calculate Binomial Coefficient (nCr) in O(r) time complexity”