आसान 0 हल किए गए 0% स्वीकृति

Binomial Coefficient

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

0 ≤ n ≤ 66

0 ≤ k ≤ 100

उदाहरण

उदाहरण 1
इनपुट:
n = 5
k = 2

अपेक्षित आउटपुट:
expected = 10
इनपुट:
long long n = 5;
long long k = 2;

अपेक्षित आउटपुट:
long long expected = 10;
इनपुट:
long n = 5;
long k = 2;

अपेक्षित आउटपुट:
long expected = 10;

व्याख्या

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

उदाहरण 2
इनपुट:
n = 6
k = 0

अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long n = 6;
long long k = 0;

अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long n = 6;
long k = 0;

अपेक्षित आउटपुट:
long expected = 1;

व्याख्या

There is exactly one way to choose nothing: 1.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।