अपने नोड्स के वजन के साथ एक बाइनरी ट्री को देखते हुए। लक्ष्य उन नोड्स की संख्या का पता लगाना है जिनका वजन इस तरह है कि उस भार में अंकों का योग एक विषम संख्या में जुड़ जाता है। यदि वजन 12 है तो अंकों का योग 3 है जो विषम है इसलिए इस नोड को गिना जाएगा।
उदाहरण के लिए
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count of nodes in the given tree whose sum of digits of weight is odd are: 2
स्पष्टीकरण
we are given with the tree node and the weights associated with each node. Now we calculate the digit sum of each and every weight and check whether it's odd or not.
| नोड | <थ>वजन <वें>योग <थ>विषम|||
|---|---|---|---|
| 2 | 23 | 2+3=5 | हां |
| 1 | 141 | 1+4+1=6 | नहीं |
| 4 | 211 | 2+1+1=4 | नहीं |
| 3 | 133 | 1+1+3=5 | हां |
| 8 | 7171 | 7+1+7+1=16 | नहीं |
| 9 | 101 | 7+0+1=8 | नहीं |
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count of nodes in the given tree whose sum of digits of weight is odd are: 4
स्पष्टीकरण
we are given with the tree node and the weights associated with each node. Now we calculate the digit sum of each and every weight and check whether it's odd or not.
| नोड | <थ>वजन <वें>योग <थ>विषम|||
|---|---|---|---|
| 2 | 5 | 5 | हां |
| 1 | 141 | 1+4+1=6 | नहीं |
| 4 | 41 | 4+1=4 | हां |
| 3 | 322 | 3+2+2=7 | हां |
| 8 | 717 | 7+1+7=15 | हां |
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम पेड़ के ग्राफ पर इसे पार करने के लिए डीएफएस लागू करेंगे और प्रत्येक नोड के वजन के अंकों के योग की जांच करेंगे, अगर यह विषम है। इस उद्देश्य के लिए दो वैक्टर Node_Weight(100) और edge_graph[100] लें।
-
नोड्स के भार के साथ Node_Weight[] प्रारंभ करें।
-
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
-
एक वैश्विक चर योग लें और इसे 0 से प्रारंभ करें।
-
फ़ंक्शन sum_total(int check) एक पूर्णांक लेता है और उसके अंकों का योग देता है।
-
प्रारंभिक योग को कुल =0 के रूप में लें।
-
थोड़ी देर के लूप का उपयोग करके चेक% 10 के रूप में सबसे दाहिने अंकों की गणना करें और इसे कुल में जोड़ें। चेक को 10 से कम करें।
-
चेक के अंकों के योग के रूप में कुल लौटाएं।
-
फ़ंक्शन ऑड_वेट (इंट नोड, इंट रूट) एक पेड़ का नोड और रूट नोड लेता है और दिए गए पेड़ में नोड्स की गिनती देता है जिसका वजन के अंकों का योग विषम होता है।
-
नोड के भार के योग के रूप में कुल =sum_total(Node_Weight[node]) की गणना करें।
-
अगर कुल%2==1 यह विषम है तो वृद्धि राशि।
-
अगर कुल%2==1 यह विषम है तो वृद्धि राशि।
-
वेक्टर में अगले नोड के लिए विषम_वेट (यह, नोड) को कॉल करें।
-
सभी कार्यों के अंत में हमारे पास विषम संख्या के रूप में अंकों के भारोत्तोलन योग के साथ नोड्स की संख्या होगी।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int sum = 0;
int sum_total(int check){
int total = 0;
while(check){
total += check % 10;
check = check / 10;
}
return total;
}
void odd_weight(int node, int root){
int total = sum_total(Node_Weight[node]);
if (total % 2 == 1){
sum++;
}
for (int it : edge_graph[node]){
if(it == root){
continue;
}
odd_weight(it, node);
}
}
int main(){
//weight of the nodes
Node_Weight[2] = 23;
Node_Weight[1] = 141;
Node_Weight[4] = 211;
Node_Weight[3] = 115;
Node_Weight[8] = 7171;
Node_Weight[9] = 701;
//create graph edge
edge_graph[2].push_back(1);
edge_graph[2].push_back(4);
edge_graph[4].push_back(3);
edge_graph[4].push_back(8);
edge_graph[8].push_back(9);
odd_weight(2, 2);
cout<<"Count the nodes in the given tree whose sum of digits of weight is odd are: "<<sum;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count the nodes in the given tree whose sum of digits of weight is odd are: 2