বাইনারি ট্রিতে অড্ড ডিজিট সম দিয়ে ওজন সম্পন্ন নোড গণনা C++-এ

একটি বাইনারি ট্রি দেওয়া আছে যার নোডগুলোর ওজন সংখ্যা হিসেবে আছে। লক্ষ্য হলো সেই নোডগুলোর সংখ্যা বের করা যাদের ওজনের ডিজিটগুলোর যোগফল একটি বিজোড় সংখ্যা (odd number)। যদি ওজন ১২ হয় তবে ডিজিট সম = ৩ যা বিজোড়, সুতরাং নোডটি গণনা হবে।

ইনপুট

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

আউটপুট

Count of nodes in the given tree whose sum of digits of weight is odd are: 2

ব্যাখ্যা

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

ইনপুট

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

আউটপুট

Count of nodes in the given tree whose sum of digits of weight is odd are: 4

ব্যাখ্যা

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

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

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

• Node_Weight[] নোডের ওজন দিয়ে ইনিশিয়ালাইজ করা হয়।
• edge_graph ভেক্টর দিয়ে ট্রি তৈরি করা হয়।
• গ্লোবাল ভেরিয়েবল sum ০ দিয়ে ইনিশিয়ালাইজ।
• sum_total(int check) ফাংশন ইন্টিজার নিয়ে এর ডিজিট সম রিটার্ন করে।
• ইনিশিয়াল সম total=0। হвайল লুপে রাইটমোস্ট ডিজিট check % 10 নিয়ে total-এ যোগ করা হয় এবং check ১০ দিয়ে ভাগ করা হয়।
• total রিটার্ন করা হয় ডিজিট সম হিসেবে।
• odd_weight(int node, int root) ফাংশন নোড এবং রুট নোড নিয়ে বিজোড় ডিজিট সম বিশিষ্ট নোড কাউন্ট রিটার্ন করে।
• total = sum_total(Node_Weight[node]) নোডের ওজনের ডিজিট সম।
• total%2==1 হলে বিজোড়, sum++।
• edge_graph[node] ট্রভারস করে রিকারসিভ কল odd_weight(it, node)।
• শেষে sum ভেরিয়েবলে প্রয়োজনীয় কাউন্ট পাওয়া যায়।

উদাহরণ

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