Find binomial co-efficient

Finding a binomial co-efficient means finding a certain combination. It is represented as nCk, which means finding k possibilities from n outcomes.

Background:
nCk = (n!) / ((n-k)! k!)
For ex: 4C2 will be 4!/(2! . 2!) = 6
So from 4 elements, there are 6 ways to pick up 2 elements. So if elements are a, b, c, d; they can be picked up as:
a, b
a, c
a, d
b, c
b, d
c, d

Approach:
4C2 = 4!/2! * 2! = (1 * 2 * 3 * 4)/ ((1 * 2) * (1 * 2))
So in numerator we are multiplying 1, 2, 3, 4. And in denominator we are multiplying 1*2, 1*2
So our numerator is something which we have to multiple to result and our denominator is something that we have to divide from result.

How to implement it:
If 4 > 4-2 then b = 4-2 = 2
i starts from 0 and goes till < b = 2.
Iteration 1: result = 1 -> result = result * (4-0) = 1 * 4. result = result / 1 = 4
Iteration 2: result = 4 -> result = result * (4-1) = 4 * 3 = 12. result = result/2 = 6

So in each iteration we are multiplying and dividing at the same time. However, we are multiplying starting from n, n-1, n-2 and so on.  And we are dividing with 1, 2, 3..till n-k. Hence the algorithm will be like the following:

Algorithm:
1) If b > n-b then b = n-b.
2) Initialize result to 1 and i to 0.
3) Perform result = result * (n-i) and result = result/(i+1)
4) Increment i by 1.
5) Repeat steps 3, 4 till i <b.

 
int findBinomialCoefficient(int b, int n) 
{
 int result = 1;
 
 if(b > n-b)
  b = n-b;

 for(int i=0; i < b; i++) 
 {
  result *= (n-i);
  result /= (i+1);
 }
 return result; 
}

You might also like:

Find White Spaces in Character Array

Find a character in the String

Number is prime or not

Finding Absolute Value

Notes on Sorting and Searching Algorithms

Common String Functions

Reverse a String

Product of all array location expect its own

Find a cycle in the Linked List

Find a binomial co-efficient

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Counting sort algorithm

B-Tree