Uma linha do triângulo de Pascal
A missão
Problema
Uma biblioteca de probabilidade precisa de todos os coeficientes binomiais de C(k, 0) até C(k, k) para um k dado, que formam a linha k do triângulo de Pascal, contando a partir da linha 0. Dado k entre 0 e 1.000, retorne essa linha como uma lista de inteiros. Construa-a em O(k) passos aritméticos, sem construir as linhas acima dela.
Exemplos
Input: k = 3
Output: [1, 3, 3, 1]
Input: k = 5
Output: [1, 5, 10, 10, 5, 1]
Input: k = 0
Output: [1]
Por quê: edge case: a linha 0 tem um único 1
Dicas
0 / 3
O elemento j da linha k é C(k, j), o número de maneiras de escolher j itens dentre k.
Ir de C(k, j) para C(k, j + 1) muda a fórmula k! / (j! (k - j)!) em um fator em cima e um fator embaixo.
C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Multiplique primeiro e depois divida com //, e a divisão é sempre exata.
- Tempo-alvo
- O(k)
- Espaço-alvo
- O(k)
Restrições
- 0 ≤ k ≤ 1000
Solução
Cada elemento da linha k é um coeficiente binomial, e coeficientes vizinhos diferem por uma razão simples: C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Partindo de C(k, 0) = 1, cada próximo elemento custa uma multiplicação e uma divisão. Multiplicar antes de dividir mantém a aritmética exata, porque C(k, j) × (k - j) é igual a C(k, j + 1) × (j + 1) e, portanto, é sempre múltiplo de j + 1, e os inteiros grandes do Python fazem com que nem o meio da linha 1.000 cause overflow. Isso evita construir as k linhas acima, o que levaria O(k²) somas. A linha leva O(k) passos aritméticos e O(k) de espaço para a saída.
def pascal_row(k):
row = [1]
for j in range(k):
row.append(row[-1] * (k - j) // (j + 1)) # exact: C(k, j+1) * (j+1)
return row
print(pascal_row(3)) # -> [1, 3, 3, 1]
print(pascal_row(5)) # -> [1, 5, 10, 10, 5, 1]
print(pascal_row(0)) # -> [1]Travou na ideia, e não no código? Permutações vs. combinações explica isso.