सभी चुनौतियाँ
आसान 0 हल किए गए 0% स्वीकृति

द्विपद गुणांक (nCk)

n वस्तुओं में से k वस्तुएँ चुनने के तरीके गिनिए (n choose k)।

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

  • फ़ैक्टोरियल के बिना संचय (combinations) निकालना
  • पास्कल का नियम लागू करना
  • k के n से बड़ा होने की स्थिति संभालना

समस्या

द्विपद गुणांक C(n, k), जिसे "n choose k" या nCk पढ़ते हैं, n अलग-अलग वस्तुओं में से k वस्तुएँ चुनने के तरीकों की संख्या है, जब क्रम मायने नहीं रखता। सूत्र n! / (k! (n − k)!) में अगर पहले फ़ैक्टोरियल निकालें तो जल्दी ही overflow हो जाता है, इसलिए उत्तर कदम-दर-कदम बनाइए या पास्कल का नियम C(n, k) = C(n − 1, k − 1) + C(n − 1, k) इस्तेमाल कीजिए।

binomial_coefficient(n, k) लिखिए।

इनपुट

n: वस्तुओं की संख्या।

k: कितनी वस्तुएँ चुननी हैं।

आउटपुट

C(n, k) लौटाइए। अगर k > n हो तो चुनने का कोई तरीका नहीं है, इसलिए 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;

व्याख्या

5 वस्तुओं में से 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;

व्याख्या

कुछ भी न चुनने का ठीक एक तरीका है: 1।

कैसे हल करें

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

संकेत 1

20 से बड़ी संख्याओं का फ़ैक्टोरियल 64 बिट्स में नहीं समाता, इसलिए उनसे बचिए।

संकेत 2

पास्कल त्रिभुज की एक पंक्ति को दाएँ से बाएँ उसी जगह पर (in place) अपडेट किया जा सकता है।

संकेत 3

C(n, k) = C(n, n − k), और k > n होने पर यह 0 है।

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

समय O(n · k), अतिरिक्त स्थान O(k)

संदर्भ

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

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

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

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

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

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