समस्या
द्विपद गुणांक 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
उदाहरण
इनपुट:
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 जोड़े बनते हैं।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।