# Binomial Coefficient Implementation in C++

## Binomial Coefficient Implementation in C++

In Binomial Coefficient as the name suggests we are required to find out the binomial coefficient ie C(n,r). Here is a c++ implementation for both top down and bottom up approach. ## Binomial Coefficient Problem Description

We are given two integers n, r. We have to find the binomial coefficient C(n,r) which is the coefficient of x^r in the expansion of (1+x)^n.

Input:

• First-line contains two integers n and r

Example:

• Given n = 5 and r = 3
• Binomial Coefficient C(5,3) = 10

Explanation

• C(5/3) = (5! )/(3! * 2!) = 120/(6*2) = 10

## Binomial Coefficient Solution Explanation

To solve the problem first we must be aware of the following relation

C(n,r) = C(n-1,r-1) + C(n-1,r)

### Solution (Top Down):

To build a top down solution we must follow the following steps –

• Break Down the Problem – For getting the value of C(n,r) we need the value of C(n-1,r-1) and C(n-1,r). This becomes our recurrence relation –

C(n,r) = C(n-1,r-1) + C(n-1,r)

• Find the base case – We know that C(n,n) = 1 & C(n,0) = 1. Also We know that in C(n,r) n>=r. So these relations will form the base case.
• Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping sub problems properties can be visualized below. ### Code C++:

#include <bits/stdc++.h>
using namespace std;
int C(int nint r)
{
if (r > n)
return 0;

if (r == 0 || r == n)
return 1;

int nCr = C(n – 1r – 1) + C(n – 1r);
return nCr;
}
int main()
{
int nr;
cout << “Enter n and r “;
cin >> n >> r;
cout << n << “C” << r << ” = “ << C(nr<< endl;
return 0;
}

### Output:

`Enter n and r 5 35C3 = 10`

### Solution (Bottom Up):

For bottom up solution we will use the smaller problems in the reverse direction. Refer to the code for more details.

### C++ Code:

#include <bits/stdc++.h>
using namespace std;
int F(int nint r)
{
if (r > n)
return 0;

int C[n + 1][r + 1];

for (int i = 0i <= ni++)
{
// j <= min(i,r) as in nCr n<=r
for (int j = 0j <= min(ir); j++)
{
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 nr;
cout << “Enter n and r “;
cin >> n >> r;
cout << n << “C” << r << ” = “ << F(nr<< endl;
return 0;
}

### Output:

`Enter n and r 5 35C3 = 10`