Problema
O coeficiente binomial C(n, k), lido "combinação de n, k a k", é o número de maneiras de escolher k itens entre n itens diferentes quando a ordem não importa. A fórmula n! / (k! (n − k)!) estoura rapidamente se você calcular os fatoriais primeiro. Por isso, monte a resposta passo a passo ou use a relação de Stifel (regra de Pascal) C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Implemente binomial_coefficient(n, k).
Entrada
n: o número de itens.
k: quantos itens escolher.
Saída
Retorne C(n, k). Se k > n, não há como escolher, então retorne 0.
Restrições
0 ≤ n ≤ 66
0 ≤ k ≤ 100
Exemplos
Entrada:
n = 5
k = 2
Saída esperada:
expected = 10
Entrada:
long long n = 5;
long long k = 2;
Saída esperada:
long long expected = 10;
Entrada:
long n = 5;
long k = 2;
Saída esperada:
long expected = 10;
Explicação
Com 5 itens, há 5 × 4 / 2 = 10 pares.
Entrada:
n = 6
k = 0
Saída esperada:
expected = 1
Entrada:
long long n = 6;
long long k = 0;
Saída esperada:
long long expected = 1;
Entrada:
long n = 6;
long k = 0;
Saída esperada:
long expected = 1;
Explicação
Existe exatamente uma maneira de não escolher nada: 1.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Fatoriais de números acima de 20 não cabem em 64 bits, então evite-os.
Dica 2
Uma linha do triângulo de Pascal pode ser atualizada no próprio lugar, da direita para a esquerda.
Dica 3
C(n, k) é igual a C(n, n − k) e vale 0 quando k > n.
Complexidade esperada
tempo O(n · k), espaço extra O(k)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.