Algorithm Coding JAVA Mathematical Algorithms

Java Programming – Space and time efficient Binomial Coefficient

Java Programming Space and time efficient Binomial Coefficient - Mathematical Algorithms - function that takes two parameters n and k and returns the value

Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.

We have discussed a O(n*k) time and O(k) extra space algorithm in this post. The value of C(n, k) can be calculated in O(k) time and O(1) extra space.

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)  // we can change r to n-r if r > n-r

Following implementation uses above formula to calculate C(n, k)

Java Program
// Program to calculate C(n ,k) in java
class BinomialCoefficient
{
    // Returns value of Binomial Coefficient C(n, k)
    static 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 program to test above function*/
    public static void main(String[] args)
    {
        int n = 8;
        int k = 2;
        System.out.println("Value of C("+ n + ", " + k+ ") "
                                + "is" + " "+ binomialCoeff(n, k));
    }
 
}
Value of C(8, 2) is 28

Time Complexity: O(k)
Auxiliary Space: O(1)

 

READ  C++ Programming-Write a program to print all permutations of a given string

About the author

Wikitechy Editor

Wikitechy Editor

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X