Problema
El coeficiente binomial C(n, k), que se lee "n sobre k", es la cantidad de formas de elegir k elementos de entre n elementos distintos cuando el orden no importa. La fórmula n! / (k! (n − k)!) se desborda enseguida si primero calculas los factoriales, así que construye la respuesta paso a paso o usa la regla de Pascal C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Implementa binomial_coefficient(n, k).
Entrada
n: la cantidad de elementos.
k: cuántos hay que elegir.
Salida
Devuelve C(n, k). Si k > n no hay forma de elegirlos, así que devuelve 0.
Restricciones
0 ≤ n ≤ 66
0 ≤ k ≤ 100
Ejemplos
Entrada:
n = 5
k = 2
Salida esperada:
expected = 10
Entrada:
long long n = 5;
long long k = 2;
Salida esperada:
long long expected = 10;
Entrada:
long n = 5;
long k = 2;
Salida esperada:
long expected = 10;
Explicación
Con 5 elementos se pueden formar 5 × 4 / 2 = 10 parejas.
Entrada:
n = 6
k = 0
Salida esperada:
expected = 1
Entrada:
long long n = 6;
long long k = 0;
Salida esperada:
long long expected = 1;
Entrada:
long n = 6;
long k = 0;
Salida esperada:
long expected = 1;
Explicación
Hay exactamente una forma de no elegir nada: 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Los factoriales de números mayores que 20 no caben en 64 bits, así que evítalos.
Pista 2
Puedes actualizar una fila del triángulo de Pascal sobre sí misma, de derecha a izquierda.
Pista 3
C(n, k) es igual a C(n, n − k), y vale 0 cuando k > n.
Complejidad esperada
tiempo O(n · k), espacio extra O(k)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.