Here the function 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!) = 10
We have discussed 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.
Approach:
- Change r to n-r if r is greater than n-r. and create a variable to store the answer.
- Run a loop from 0 to r-1
- In every iteration update ans as (ans*(n-i))/(i+1) where i is the loop counter.
- So the answer will be equal to ((n/1)*((n-1)/2)*…*((n-r+1)/r) which is equal to nCr.
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
Following implementation uses the above formula to calculate C(n, k).
C++
// 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; } // This is code is contributed by rathbhupendra |
C
// Program to calculate C(n, k) #include <stdio.h> // 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 program to test above function*/int main() { int n = 8, k = 2; printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k)); return 0; } |
Java
// 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)); } } // This Code is Contributed by Saket Kumar |
Python3
# Python program to calculate C(n, k) # Returns value of Binomial Coefficient # C(n, k) def binomialCoefficient(n, k): # since C(n, k) = C(n, n - k) if(k > n - k): k = n - k # initialize result res = 1 # Calculate value of # [n * (n-1) *---* (n-k + 1)] / [k * (k-1) *----* 1] for i in range(k): res = res * (n - i) res = res // (i + 1) return res # Driver program to test above function n = 8k = 2res = binomialCoefficient(n, k) print("Value of C(% d, % d) is % d" %(n, k, res)) # This code is contributed by Aditi Sharma |
C#
// C# Program to calculate C(n, k) using System; 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 Code public static void Main() { int n = 8; int k = 2; Console.Write("Value of C(" + n + ", " + k + ") " + "is" + " " + binomialCoeff(n, k)); } } // This Code is Contributed by // Smitha Dinesh Semwal. |
PHP
<?php // Program to calculate C(n, k) // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff($n, $k) { $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 ($i = 0; $i < $k; ++$i) { $res *= ($n - $i); $res /= ($i + 1); } return $res; } // Driver Code $n = 8; $k = 2; echo " Value of C ($n, $k) is ", binomialCoeff($n, $k); // This code is contributed by ajit. ?> |
Javascript
<script> // Program to calculate C(n, k) // Returns value of Binomial Coefficient C(n, k) function binomialCoeff(n, k) { let 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 (let i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver Code let n = 8; let k = 2; document.write("Value of C(" + n + ", " + k + ") " + "is" + " " + binomialCoeff(n, k)); </script> |
Output
Value of C(8, 2) is 28
Complexity Analysis:
Time Complexity: O(r) A loop has to be run from 0 to r. So, the time complexity is O(r).
Auxiliary Space: O(1) As no extra space is required.
This article is compiled by Aashish Barnwal and reviewed by the neveropen team. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
