मान लीजिए हमारे पास सकारात्मक पूर्णांकों की एक सूची है; जिनका मान 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]])
- यदि A[i] mod A[j] = 0, तो
- 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