पायथन में 0 से n मानों के साथ बनने वाले अद्वितीय बाइनरी सर्च ट्री की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या n है, हमें उन अद्वितीय BST की संख्या ढूंढनी है जिन्हें हम [0, n) से संख्याओं के साथ उत्पन्न कर सकते हैं। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9+7 से मॉड करें।

उदाहरण के लिए, यदि इनपुट n = 3 है, तो आउटपुट 5 होगा।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• numer := 1
• denom := n + 1
• i को 1 से n तक के लिए करें:
  • numer := numer * (n + i)
  • numer := numer % m
  • denom := denom * i
  • denom := denom % m
• numer := numer * (denom^(m-2)) % m
• numer % m वापस करें

उदाहरण

class Solution:
    def solve(self, n):
        m = 10**9 + 7
        numer = 1
        denom = n + 1
        for i in range(1, n+1):
            numer *= n + i
            numer %= m
            denom *= i
            denom %= m
        numer *= pow(denom, m-2, m)
        return numer % m
ob = Solution()
print(ob.solve(4))

इनपुट

4

आउटपुट

14