C++-এ ফ্যাক্টর সহ বাইনারি ট্রি গণনা

মান করুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যার তালিকা দেওয়া আছে যeren মান ১-এর চেয়ে বড়। আমরা এই পূর্ণসংখ্যাগুলো ব্যবহার করে একটি বাইনারি ট্রি তৈরি করব, এবং প্রতিটি সংখ্যা যেকোনো সংখ্যকবার ব্যবহার করা যাবে। প্রতিটি নন-লিফ নোড অবশ্যই তার চাইল্ডদের গুণফলের সমান হবে। আমাদের বের করতে হবে কতগুলো ট্রি তৈরি করা সম্ভব? উত্তর 10^9 + 7 মডুলোতে ফেরত দিতে হবে।

যদি ইনপুট হয় [2,4,5,10], তবে উত্তর হবে ৭, কারণ আমরা ৭টি ট্রি তৈরি করতে পারি: [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 থেকে i - 1 পর্যন্ত
  - যদি A[i] % A[j] == 0 হয়, তবে
    - dp[A[i]] := dp[A[i]] + (dp[A[j]] * dp[A[i] / 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]

C++-এ ফ্যাক্টর সহ বাইনারি ট্রি গণনা

উদাহরণ কোড

ইনপুট

আউটপুট