Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में गुणनखंडों के साथ बाइनरी ट्री


मान लीजिए हमारे पास सकारात्मक पूर्णांकों की एक सूची है; जिनका मान 1 से अधिक है। हम इन पूर्णांकों का उपयोग करके एक बाइनरी ट्री बनाएंगे, और प्रत्येक संख्या का उपयोग जितनी बार चाहें उतनी बार किया जा सकता है। प्रत्येक नॉन-लीफ नोड को उसके बच्चों का गुणनफल होना चाहिए। तो हमें यह पता लगाना है कि हम कितने ट्री बना सकते हैं? उत्तर को मॉड्यूलो 10^9 + 7 में लौटाया जाएगा। तो यदि इनपुट [2,4,5,10] जैसा है, तो उत्तर 7 होगा, क्योंकि हम 7 ट्री बना सकते हैं जैसे [2], [4], [5], [10], [4,2,2], [10,2,5], [10,5,2]

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

  • एक मैप dp परिभाषित करें
  • सरणी A को सॉर्ट करें, n := सरणी A का आकार, ret := 0
  • i को 0 से n - 1 की रेंज में
    • dp[A[i]] को 1 से बढ़ाएं
    • j को 0 से j - 1 की रेंज में
      • यदि A[i] mod A[j] = 0, तो
        • dp[A[i]] := dp[A[i]] + (dp[A[j]] * dp[A[i]] / dp[A[j]])
    • ret := ret + dp[A[i]]
  • ret लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;
const int MOD = 1e9 + 7;

int add(lli a, lli b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

int mul(lli a, lli b){
    return ((a % MOD) * (b % MOD)) % MOD;
}

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        unordered_map <int, int> dp;
        sort(A.begin(), A.end());
        int n = A.size();
        int ret = 0;
        for(int i = 0; i < n; i++){
            dp[A[i]] += 1;
            for(int j = 0; j < i; j++){
                if(A[i] % A[j] == 0){
                    dp[A[i]] = add(dp[A[i]], mul(dp[A[j]], dp[A[i] / A[j]]));
                }
            }
            ret = add(ret, dp[A[i]]);
        }
        return ret;
    }
};

main(){
    vector<int> v1 = {2,4,5,10};
    Solution ob;
    cout << (ob.numFactoredBinaryTrees(v1));
}

इनपुट

[2,4,5,10]

आउटपुट

7

  1. C++ में अद्वितीय बाइनरी सर्च ट्री C++ में अद्वितीय बाइनरी सर्च ट्री

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री की गिनती करनी है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो आउटपुट 5 होगा, क्योंकि ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:आ

  1. C++ में अद्वितीय बाइनरी सर्च ट्री II C++ में अद्वितीय बाइनरी सर्च ट्री II

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री को उत्पन्न करना है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:generate() नामक एक पुन

  1. C++ में दो बाइनरी ट्री को मर्ज करना C++ में दो बाइनरी ट्री को मर्ज करना

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं और जब हम एक को दूसरे पर ओवरलैप करते हैं, तो कुछ नोड्स ओवरलैप होते हैं जबकि अन्य नहीं। हमें इन्हें एक नए बाइनरी ट्री में मर्ज करना है। मर्ज का नियम यह है कि यदि दो नोड्स ओवरलैप होते हैं, तो उनके मानों को जोड़कर मर्ज किए गए नोड का नया मान बनाया जाता है। अन्यथा,