এর নোডগুলির ওজন সহ একটি বাইনারি গাছ দেওয়া হয়েছে৷ লক্ষ্য হল নোডের সংখ্যা খুঁজে বের করা যার ওজন আছে যাতে সংখ্যাটি দুইটির শক্তি। যদি ওজন 32 হয় তবে এটি 25 হয় তাই এই নোডটি গণনা করা হবে।
উদাহরণস্বরূপ
ইনপুট
মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল -
আউটপুট
Count the nodes in the given tree whose weight is a power of two are: 3
ব্যাখ্যা
we are given with the tree node and the weights associated with each node. Now we calculate the power of each and every weight and check whether it can be expressed as power of 2 or not.
| নোড | ওজন | ওজন^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
ব্যাখ্যা
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 | পাওয়ার অফ 2 |
|---|---|---|---|
| 2 | 16 | 4^2 | হ্যাঁ |
| 1 | 141 | সম্ভব নয় | না |
| 4 | 41 | প্রধান সংখ্যা | না |
| 3 | 64 | 8^2 | হ্যাঁ |
| 8 | 81 | 9^2 | হ্যাঁ |
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা গাছের গ্রাফে ডিএফএস প্রয়োগ করব যাতে এটিকে অতিক্রম করা যায় এবং নোডের ওজন 2 এর শক্তি কিনা তা পরীক্ষা করে দেখুন। এই উদ্দেশ্যে দুটি ভেক্টর Node_Weight(100) এবং edge_graph[100] নিন।
-
নোডের ওজন দিয়ে নোড_ওয়েট[] শুরু করুন।
-
ভেক্টর এজ_গ্রাফ ব্যবহার করে একটি গাছ তৈরি করুন।
-
একটি বৈশ্বিক পরিবর্তনশীল যোগফল নিন এবং এটি 0 দিয়ে শুরু করুন।
-
ফাংশন পাওয়ার_টু(int নোড, int রুট) একটি গাছের একটি নোড এবং রুট নোড নেয় এবং প্রদত্ত গাছে নোডের গণনা ফেরত দেয় যার ওজন দুইটির শক্তি।
-
সেট নিন =নোড_ওয়েট[নোড];
-
যদি সেট &&(!(সেট এবং (সেট −1))) সত্য ফেরত দেয় তবে এটি দুটির শক্তি (বিটওয়াইজ এবং তারপর নেগেশান)
-
সেট হিসাবে শক্তি বৃদ্ধির একটি মান রয়েছে যা 2 এর শক্তি।
-
লুপের জন্য ব্যবহার করে ভেক্টর এজ_গ্রাফ[নোড] এ ট্র্যাভার্স ট্রি।
-
ভেক্টরের পরবর্তী নোডের জন্য power_two(এটি, নোড) কল করুন।
-
সমস্ত ফাংশনের শেষে আমাদের কাছে নোডের সংখ্যা হিসাবে পাওয়ার থাকবে যার ওজনের দুটি পাওয়ার হিসাবে মান থাকবে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> 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
