Find the maximum GCD of the siblings of a Binary Tree using C++
GCD (Greatest Common Divisor) is the largest number that divides two numbers. In this tutorial, we will find the maximum GCD of the siblings of a binary tree using C++.
The vector datatype is used to store the tree. The pairs are made of the parent node and child node and stored in vector. If the size of vector is 0 or 1 then there is no GCD since no node or only one node is present. If it is greater than 1 then it will compare with the next. if they have same parent nodes then their GCD is stored in a variable and maximum gcd of all the nodes is displayed.
C++ Code for Maximum GCD of the siblings of a binary tree
#include <iostream> #include<vector> #include <algorithm> using namespace std; int gcdmax(vector<pair<int, int>> &a) { if(a.size()==1 || a.size()==0) return 0; pair<int, int> x = a[0]; pair<int, int> y; int r=-999999; for (int i=1;i<a.size();i++) { y=a[i]; if(x.first == y.first) { r= std :: max(r,__gcd(x.second,y.second)); } x=y; } return(r); } int main() { int ch,p,c; int res,y=5; vector<pair<int, int> >a; do{ cout << "Enter 1 to continue entering and 2 to exit" << endl; cin>>ch; switch(ch) {case 1: cout<< "Enter the parent" << endl; cin>>p; cout<<"Enter the child" <<endl; cin>>c; a.push_back(make_pair(p, c)); break; case 2: y=10; res= gcdmax(a); cout<<res; break; } }while(y!=10); return 0; }
After running the above program, we get the following output:
Enter 1 to continue entering and 2 to exit 1 Enter the parent 5 Enter the child 2 Enter 1 to continue entering and 2 to exit 1 Enter the parent 5 Enter the child 7 Enter 1 to continue entering and 2 to exit 1 Enter the parent 2 Enter the child 9 Enter 1 to continue entering and 2 to exit 1 Enter the parent 9 Enter the child 15 Enter 1 to continue entering and 2 to exit 1 Enter the parent 9 Enter the child 27 Enter 1 to continue entering and 2 to exit 1 Enter the parent 7 Enter the child 13 Enter 1 to continue entering and 2 to exit 2 Maximum GCD is: 3
The example tree that is considered above is = {[5,2],[5,7],[2,9],[9,15],[9,27],[7,13]}
Output is 3.
Leave a Reply