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

आउटपुट
Count the nodes in the given tree whose weight is a power of two are: 3
व्याख्या
हमें ट्री नोड और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम प्रत्येक वजन की घात की गणना करते हैं और जांचते हैं कि क्या इसे 2 की घात के रूप में व्यक्त किया जा सकता है या नहीं।
| नोड | वजन | वजन^2 | 2 की घात |
|---|---|---|---|
| 2 | 8 | 2*2*2 | नहीं |
| 1 | 100 | 10*2 | हां |
| 4 | 211 | अभाज्य संख्या | नहीं |
| 3 | 16 | 4^2 | हां |
| 8 | 1717 | संभव नहीं | नहीं |
| 9 | 32 | 2*2*2*2*2 | हां |
इनपुट
मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count the nodes in the given tree whose weight is a power of two are: 3
व्याख्या
हमें ट्री नोड और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम प्रत्येक वजन का अंक योग निकालते हैं और जांचते हैं कि यह विषम है या नहीं।
| नोड | वजन | वजन ^ 2 | 2 की घात |
|---|---|---|---|
| 2 | 16 | 4^2 | हां |
| 1 | 141 | संभव नहीं | नहीं |
| 4 | 41 | अभाज्य संख्या | नहीं |
| 3 | 64 | 8^2 | हां |
| 8 | 81 | 9^2 | हां |
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम ट्री के ग्राफ पर DFS लागू करेंगे इसे ट्रैवर्स करने के लिए और जांचेंगे कि क्या नोड्स का वजन 2 की घात है। इस उद्देश्य के लिए दो वेक्टर Node_Weight(100) और edge_graph[100] लें।
Node_Weight[] को नोड्स के वजन से इनिशियलाइज़ करें।
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
एक ग्लोबल वेरिएबल sum लें और इसे 0 से इनिशियलाइज़ करें।
फ़ंक्शन power_two(int node, int root) एक नोड और ट्री का रूट नोड लेता है और दिए गए ट्री में उन नोड्स की संख्या लौटाता है जिनका वजन दो की घात है।
set = Node_Weight[node] लें।
यदि set && (!(set & (set - 1))) ट्रू लौटाता है तो यह दो की घात है (बिटवाइज़ AND और फिर नेगेशन)।
powers बढ़ाएं क्योंकि set का मान 2 की घात है।
फॉर लूप का उपयोग करके वेक्टर edge_graph[node] में ट्री को ट्रैवर्स करें।
वेक्टर में अगले नोड के लिए power_two(it, node) कॉल करें।
सभी फ़ंक्शन के अंत में हमारे पास power उन नोड्स की संख्या के रूप में होगा जिनके वजन का मान दो की घात है।
उदाहरण
#include <bits/stdc++.h> using namespace std; vectorNode_Weight(100); vector edge_graph[100]; int powers = 0; void power_two(int node, int root){ int set = Node_Weight[node]; if(set && (!(set & (set - 1)))){ powers++; } for(int it : edge_graph[node]){ if(it == root){ continue; } power_two(it, node); } } int main(){ //weight of the nodes Node_Weight[2] = 8; Node_Weight[1] = 100; Node_Weight[4] = 211; Node_Weight[3] = 16; Node_Weight[8] = 7171; Node_Weight[9] = 32; //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); power_two(2, 2); cout<<"Count the nodes in the given tree whose weight is a power of two are: "<<powers; return 0; }
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count the nodes in the given tree whose weight is a power of two are: 3