नोड्स के वजन वाली एक बाइनरी ट्री दी गई है। लक्ष्य उन नोड्स की संख्या ढूंढना है जिनके वजन ऐसे हैं कि उस वजन में अंकों का योग एक विषम संख्या तक जुड़ता है। यदि वजन 12 है तो अंक योग 3 है जो विषम है इसलिए यह नोड गिना जाएगा।
उदाहरण के लिए
इनपुट
मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count of nodes in the given tree whose sum of digits of weight is odd are: 2
व्याख्या
हमें ट्री नोड और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम प्रत्येक वजन का अंक योग निकालते हैं और जांचते हैं कि यह विषम है या नहीं।
| नोड | वजन | योग | विषम |
|---|---|---|---|
| 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
व्याख्या
हमें ट्री नोड और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम प्रत्येक वजन का अंक योग निकालते हैं और जांचते हैं कि यह विषम है या नहीं।
| नोड | वजन | योग | विषम |
|---|---|---|---|
| 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 | हां |
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम ट्री के ग्राफ पर DFS लागू करेंगे इसे ट्रैवर्स करने के लिए और प्रत्येक नोड के वजन के अंकों के योग की जांच करेंगे, यदि यह विषम है। इस उद्देश्य के लिए दो वेक्टर Node_Weight(100) और edge_graph[100] लें।
Node_Weight[] को नोड्स के वजन से इनिशियलाइज़ करें।
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
एक ग्लोबल वेरिएबल sum लें और इसे 0 से इनिशियलाइज़ करें।
फ़ंक्शन sum_total(int check) एक पूर्णांक लेता है और उसके अंकों का योग लौटाता है।
प्रारंभिक योग को total=0 के रूप में लें।
व्हाइल लूप का उपयोग करके दाहिने सबसे अंक को check % 10 के रूप में गणना करें और इसे total में जोड़ें। check को 10 से कम करें।
total को check के अंकों के योग के रूप में लौटाएं।
फ़ंक्शन odd_weight(int node, int root) एक नोड और ट्री का रूट नोड लेता है और दिए गए ट्री में उन नोड्स की संख्या लौटाता है जिनके वजन के अंकों का योग विषम है।
total = sum_total(Node_Weight[node]) की गणना करें नोड के वजन के योग के रूप में।
यदि total%2==1 तो यह विषम है तो sum बढ़ाएं।
यदि total%2==1 तो यह विषम है तो sum बढ़ाएं।
वेक्टर में अगले नोड के लिए odd_weight(it, node) कॉल करें।
सभी फ़ंक्शन के अंत में हमारे पास sum उन नोड्स की संख्या के रूप में होगा जिनके वजन के अंकों का योग विषम संख्या है।
उदाहरण
#include <bits/stdc++.h> using namespace std; vectorNode_Weight(100); vector 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