নোডের ওজন সহ একটি বাইনারি গাছ দেওয়া হয়েছে। লক্ষ্য হল নোডের সংখ্যা খুঁজে বের করা যার ওজন আছে যাতে সেই ওজনের সংখ্যার যোগফল একটি বিজোড় সংখ্যার সাথে যোগ হয়। যদি ওজন 12 হয় তাহলে অঙ্কের যোগফল 3 যা বিজোড় তাই এই নোডটি গণনা করা হবে৷
উদাহরণস্বরূপ
ইনপুট
মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল -
আউটপুট
Count of nodes in the given tree whose sum of digits of weight is odd are: 2
ব্যাখ্যা
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.
| নোড | ওজন | সমষ্টি | ODD |
|---|---|---|---|
| 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
ব্যাখ্যা
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.
| নোড | ওজন | সমষ্টি | ODD |
|---|---|---|---|
| 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 | হ্যাঁ |
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা গাছের গ্রাফে ডিএফএস প্রয়োগ করব যাতে এটি অতিক্রম করা যায় এবং প্রতিটি নোডের ওজনের অঙ্কের যোগফল পরীক্ষা করে দেখব, যদি এটি বিজোড় হয়। এই উদ্দেশ্যে দুটি ভেক্টর নোড_ওয়েট(100) এবং এজ_গ্রাফ[100] নিন।
-
নোডের ওজন দিয়ে নোড_ওয়েট[] শুরু করুন।
-
ভেক্টর এজ_গ্রাফ ব্যবহার করে একটি গাছ তৈরি করুন।
-
একটি বৈশ্বিক পরিবর্তনশীল যোগফল নিন এবং এটি 0 দিয়ে শুরু করুন।
-
ফাংশন sum_total(int check) একটি পূর্ণসংখ্যা নেয় এবং এর সংখ্যার যোগফল প্রদান করে।
-
মোট =0 হিসাবে প্রাথমিক যোগফল নিন।
-
কিছুক্ষণ লুপ ব্যবহার করে চেক % 10 হিসাবে ডানদিকের সংখ্যাগুলি গণনা করুন এবং এটিকে মোট যোগ করুন৷ চেক 10 দ্বারা হ্রাস করুন৷
-
চেকের অঙ্কের যোগফল হিসাবে মোট রিটার্ন করুন।
-
ফাংশন odd_weight(int নোড, int root) একটি গাছের একটি নোড এবং রুট নোড নেয় এবং প্রদত্ত গাছে নোডের সংখ্যা ফেরত দেয় যার ওজনের অঙ্কের যোগফল বিজোড়।
-
নোডের ওজনের যোগফল হিসাবে মোট =যোগ_মোট(নোড_ওজন[নোড]) গণনা করুন।
-
যদি মোট%2==1 এর বিজোড় হয় তাহলে যোগফল বৃদ্ধি করুন।
-
যদি মোট%2==1 এর বিজোড় হয় তাহলে যোগফল বৃদ্ধি করুন।
-
ভেক্টরের পরবর্তী নোডের জন্য odd_weight(এটি, নোড) কল করুন।
-
সমস্ত ফাংশনের শেষে আমাদের কাছে নোডের সংখ্যা হিসাবে যোগফল থাকবে এবং বিজোড় সংখ্যা হিসাবে অঙ্কের যোগফল ওজন শেভ করা হবে।
উদাহরণ
#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(){
//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
