একটি n-ary গাছ এবং একটি সংখ্যা দেওয়া হলে, আমাদের প্রদত্ত সংখ্যার চেয়ে বড় নোডের সংখ্যা গণনা করতে হবে। আসুন একটি উদাহরণ দেখি।
ইনপুট
tree = [[4], [1, 2], [3, 5]] n = 2
আউটপুট
3
n-এর চেয়ে বড় মান সহ 3টি নোড রয়েছে।
অ্যালগরিদম
-
এন-আরি ট্রি শুরু করুন।
-
গণনা শুরু করুন 0।
-
1 দ্বারা গণনা বৃদ্ধি করুন যখন আপনি একটি নোড খুঁজে পান যার মান n এর চেয়ে বেশি।
-
বর্তমান নোডের শিশুদের পান।
-
সমস্ত শিশুর উপর পুনরাবৃত্তি করুন এবং নোড গণনা করতে একই ফাংশনকে বারবার কল করুন।
-
গণনা ফেরত দিন।
বাস্তবায়ন
C++
-এ উপরের অ্যালগরিদমের বাস্তবায়ন নিচে দেওয়া হল#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node*> child;
};
Node* getNewNode(int data) {
Node* temp = new Node;
temp->data = data;
return temp;
}
int getGreaterElementsCount(Node* root, int n) {
if (root == NULL)
return 0;
int count = 0;
if (root->data > n) {
count++;
}
int nodeChildrenCount = root->child.size();
for (int i = 0; i < nodeChildrenCount; i++) {
Node* child = root->child[i];
count += getGreaterElementsCount(child, n);
}
return count;
}
int main() {
Node* root = getNewNode(1);
(root->child).push_back(getNewNode(2));
(root->child).push_back(getNewNode(3));
(root->child).push_back(getNewNode(4));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(7));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(9));
int n = 2;
cout << getGreaterElementsCount(root, n) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
10
