मान लीजिए हमें कई बार nCr मानों की गणना करनी है। हम इसे बहुत कुशल तरीके से हल कर सकते हैं। यदि हम nCr के निचले मानों को संग्रहीत करते हैं तो हम आसानी से उच्च मान खोज सकते हैं। तो यदि हमारे पास n है, तो हमें nC0 से nCn तक की सूची खोजनी है। यदि उत्तर बहुत बड़ा है तो उसे मॉड्यूलो 10^9 लौटाएं।
तो, यदि इनपुट n = 6 है, तो आउटपुट [1, 6, 15, 20, 15, 6, 1] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- items := एकल तत्व 1 वाली एक सूची
- r को 1 से n तक की रेंज में, करें
- items के अंतिम तत्व * (n-r+1) /r के फ्लोर को items के अंत में डालें
- items[n-2] := items[n-2] mod 10^9 जहां n, items का आकार है
- items लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(n): items = [1] for r in range(1,n+1): items.append(items[-1]*(n-r+1)//r) items[-2] %= 10**9 return items n = 6 print(solve(n))
इनपुट
6
आउटपुट
[1, 6, 15, 20, 15, 6, 1]
