-->

Efficient Binomial Coefficient

Posted by Admin on
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k).
For example:-
if k=8 , n= 2 result should be 28.

Solution

If you dont know much about binomial coefficient then please first see http://en.wikipedia.org/wiki/Binomial_coefficient

The value of C(n,k) is calculated as :-

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) *                                                                 ( k * (k-1) * .... * 1 ) ]
But if you have noticed then the above equation can be simplified as follows:-

C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]


Above equation is the main logic behind the efficient solution of binomial cofficient.  

Also we know that 
C(n, k) is equal  to  C(n, n-k)   

Implementation :-

public class BinomialCofficient {
       public static void main(String args[]) {
              int n = 8;
              int k = 2;
              int result = findingNCK(k, n);
              System.out.println(result);
       }

       public static int findingNCK(int k, int n) {
              int result = 1;
              /*
               * As we know C(n,k)=C(n,n-k) if k> n-k then make k =n-k so that we need
               * to run loop less
               */
              if (k > n - k)
                     k = n - k;
              int i = 0;
              while (i < k) {
                     result = result * (n - i);
                     result = result / (i + 1);
                     i++;
              }
              return result;
       }
}

 Time Complexity : O(k)






No comments:

Post a Comment