Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Coeficiente binomial

Conte de quantas maneiras é possível escolher k itens entre n (combinação de n, k a k).

O que você vai aprender

  • Calcular combinações sem fatoriais
  • Aplicar a relação de Stifel
  • Tratar k maior que n

Problema

Ver original (inglês)

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

Exemplo 1
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.

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.