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

Your email address will not be published. Required fields are marked *