Problem Statement

Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). Example:

Input: n = 4 and k = 2
Output: 6
Explanation: 4 C 2 is 4!/(2!*2!) = 6

Input: n = 5 and k = 2
Output: 10
Explanation: 5 C 2 is 5!/(3!*2!) = 20

Problem Link

Space and time efficient Binomial Coefficient - GeeksforGeeks

Approach

C(n, k)
= n! / (n-k)! * k!
= [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) *
                            ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k)
= [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)
// r can be changed to n-r if r > n-r

Code

// Program to calculate C(n, k)
#include <bits/stdc++.h>
using namespace std;

// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
	int res = 1;

	// Since C(n, k) = C(n, n-k)
	if (k > n - k)
		k = n - k;

	// Calculate value of
	// [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
	for (int i = 0; i < k; ++i) {
		res *= (n - i);
		res /= (i + 1);
	}

	return res;
}

// Driver Code
int main()
{
	int n = 8, k = 2;
	cout << "Value of C(" << n << ", "
		<< k << ") is " << binomialCoeff(n, k);
	return 0;
}

// Time complexity : O(n)