বাইনারি ট্রিতে ২-এর ঘাত বিশিষ্ট ওজন সম্পন্ন নোড গণনা C++-এ

একটি বাইনারি ট্রি দেওয়া আছে যার নোডগুলোর ওজন সংখ্যা হিসেবে আছে। লক্ষ্য হলো সেই নোডগুলোর সংখ্যা বের করা যাদের ওজন ২-এর ঘাত (power of two)। যদি ওজন ৩২ হয় তবে সেটি ২⁵, সুতরাং নোডটি গণনা হবে।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes in the given tree whose weight is a power of two are: 3

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন প্রতিটি ওজনের ঘাত গণনা করে চেক করা হচ্ছে এটা ২-এর ঘাত হিসেবে এক্সপ্রেস করা যায় কিনা।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes in the given tree whose weight is a power of two are: 3

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন প্রতিটি ওজনের ডিজিট সম গণনা করে চেক করা হচ্ছে এটা অড্ড কিনা।

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

এই পদ্ধতিতে আমরা ট্রির গ্রাফে DFS অ্যাপ্লাই করি ট্রভারস করতে এবং চেক করি নোডের ওজন ২-এর ঘাত কিনা। দুটি ভেক্টর Node_Weight(100) এবং edge_graph[100] নেওয়া হয়।

• Node_Weight[] নোডের ওজন দিয়ে ইনিশিয়ালাইজ করা হয়।
• edge_graph ভেক্টর দিয়ে ট্রি তৈরি করা হয়।
• গ্লোবাল ভেরিয়েবল sum (এখানে powers) ০ দিয়ে ইনিশিয়ালাইজ।
• power_two(int node, int root) ফাংশন নোড এবং রুট নোড নিয়ে ২-এর ঘাত ওজন বিশিষ্ট নোড কাউন্ট রিটার্ন করে।
• set = Node_Weight[node] নেওয়া হয়।
• set && (!(set & (set - 1))) true হলে সেটি ২-এর ঘাত (বিটওয়াইজ AND এবং নেগেশন)।
• powers++ বাড়ানো হয়।
• edge_graph[node] ট্রভারস করে রিকারসিভ কল power_two(it, node)।
• শেষে powers ভেরিয়েবলে প্রয়োজনীয় কাউন্ট পাওয়া যায়।

উদাহরণ

#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() {
    // নোডের ওজন
    Node_Weight[2] = 8;
    Node_Weight[1] = 100;
    Node_Weight[4] = 211;
    Node_Weight[3] = 16;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 32;
    // গ্রাফ এজ তৈরি
    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