40 lines
1.0 KiB
C++
40 lines
1.0 KiB
C++
|
// C++ code to find the Binomial Coefficient
|
||
|
|
// Description: Given two parameters n and r, find the value of the Binomial Coefficient i.e. C(n, r)
|
||
|
|
// Method: Change r to n-r if r is greater than n-r and store it in a variable. Run a loop from 0 to r-1 and in every iteration update result to be (ans*(n-i))/(i+1). Hence, the result will be ((n/1)*((n-1)/2)*…*((n-r+1)/r!) i.e. nCr.
|
||
|
|
// Time Complexity: O(r)
|
||
|
|
// Space Complexity: O(1)
|
||
|
|
|
||
|
|
#include <bits/stdc++.h>
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
int findBinCoeff(int n, int r)
|
||
|
|
{
|
||
|
|
int result = 1;
|
||
|
|
|
||
|
|
if (r > n - r)
|
||
|
|
{
|
||
|
|
r = n - r; // C(n, r) = C(n, n-r)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Find [n*(n-1)*...*(n-r+1)]/[r*(r-1)*...*1]
|
||
|
|
for (int i = 0; i < r; ++i)
|
||
|
|
{
|
||
|
|
result = result * (n - i);
|
||
|
|
result = result / (i + 1);
|
||
|
|
}
|
||
|
|
return result;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main()
|
||
|
|
{
|
||
|
|
int n;
|
||
|
|
cout << "Enter the value of n: ";
|
||
|
|
cin >> n; // Eg value of n: 6
|
||
|
|
int r;
|
||
|
|
cout << "Enter the value of r: ";
|
||
|
|
cin >> r; // Eg value of r: 2
|
||
|
|
// C(6,2) = 6!/(4!*2!) = 15
|
||
|
|
cout << "The Binomial Coefficient is: ";
|
||
|
|
cout << findBinCoeff(n, r) << endl; //Eg output: 15
|
||
|
|
return 0;
|
||
|
|
}
|