Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Binomial Coefficient

Count the ways to choose k items out of n (n choose k).

Das lernst du

  • Compute combinations without factorials
  • Apply Pascal's rule
  • Handle k greater than n

Problem

Übersetzung anzeigen

The binomial coefficient C(n, k), read "n choose k", is the number of ways to pick k items from n different items when order does not matter. The formula n! / (k! (n − k)!) overflows quickly if you compute the factorials first, so build the answer step by step or use Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Implement binomial_coefficient(n, k).

Input

n: The number of items.

k: How many to choose.

Output

Return C(n, k). If k > n there is no way to choose, so return 0.

Einschränkungen

0 ≤ n ≤ 66

0 ≤ k ≤ 100

Beispiele

Beispiel 1
Eingabe:
n = 5
k = 2

Erwartete Ausgabe:
expected = 10
Eingabe:
long long n = 5;
long long k = 2;

Erwartete Ausgabe:
long long expected = 10;
Eingabe:
long n = 5;
long k = 2;

Erwartete Ausgabe:
long expected = 10;

Erläuterung

The pairs from 5 items number 5 × 4 / 2 = 10.

Beispiel 2
Eingabe:
n = 6
k = 0

Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 6;
long long k = 0;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 6;
long k = 0;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

There is exactly one way to choose nothing: 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Factorials of numbers above 20 do not fit in 64 bits, so avoid them.

Hinweis 2

One row of Pascal's triangle can be updated in place from right to left.

Hinweis 3

C(n, k) equals C(n, n − k), and it is 0 when k > n.

Erwartete Komplexität

O(n · k) time, O(k) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.