Coeficiente binomial eficiente en espacio y tiempo

Escriba una función que tome dos parámetros n y k y devuelva el valor del coeficiente binomial C(n, k). 
Ejemplo: 
 

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

Hemos discutido un algoritmo de tiempo O(n*k) y espacio adicional O(k) en esta publicación. El valor de C(n, k) se puede calcular en O(k) tiempo y O(1) espacio adicional.
 

// 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

// 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;
}

// 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

# 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 = 8
k = 2
res = binomialCoefficient(n, k)
print("Value of C(% d, % d) is % d" %(n, k, res))
 
# This code is contributed by Aditi Sharma

// 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
// 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.
?>

<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>