Finding the gcd of Each Sibling of the Binary Tree

Implementation

// Writing a C++ program to determine the maximum GCD of the siblings in an array.  
#include <bits/stdc++.h>
using namespace std;


// writing a function to find the maximum GCD
int max_gcd(vector<pair<int, int> >& v)
{
	// If there is no child or a single child
	if (v.size() == 1 || v.size() == 0)
		return 0;


	sort(v.begin(), v.end());


	// now, we have to find the first pair
	pair<int, int> a = v[0];
	pair<int, int> b;
	int ans = INT_MIN;
	for (int i = 1; i < v.size(); i++) {
		b = v[i];


		// Suppose both the pairs of the node belong to the same node or the parent node. 
		if (b.first == a.first)


// Now, we will begin by updating the ans with both children's maximum current and gcd. 
			ans
				= max(ans,
					__gcd(a.second,
							b.second));


		// now we will begin by updating the next iteration
		a = b;
	}
	return ans;
}


// writing the main code to test the above program. 
int main()
{
	vector<pair<int, int> > v;
	v.push_back(make_pair(5, 4));
	v.push_back(make_pair(5, 8));
	v.push_back(make_pair(4, 6));
	v.push_back(make_pair(4, 9));
	v.push_back(make_pair(8, 10));
	v.push_back(make_pair(10, 20));
	v.push_back(make_pair(10, 30));


	cout << max_gcd(v);
	return 0;
}

Output:

Example 2

// Writing a C# program to determine the maximum GCD of the siblings in the array.  
using System.Collections;
using System;


class TFT{
// writing a function to find the maximum GCD
static int max_gcd(ArrayList v)
{
	// If there is no child or a single child
	if (v.Count == 1 || v.Count == 0)
		return 0;


	v.Sort();
	// now, we have to find the first pair
	int[] a = (int [])v[0];
	int[] b = new int[2];
	int ans = -10000000;
	
	for(int i = 1; i < v.Count; i++)
	{
	b = (int[])v[i];
	// Suppose both the pairs of the node belong to the same node or the parent node. 
	if (b[0] == a[0])
		// Now we will begin by updating the ans with the maximum of the current and gcd of both children. 
		Ans = Math.Max(ans, gcd(a[1], b[1]));
		// now we will begin by updating the next iteration
	a = b;
	}
	return ans;
}


static int gcd(int a, int b)
{
	if (b == 0)
		return a;
		
	return gcd(b, a % b);
}
// writing the main code to test the above program.
public static void Main(string[] args)
{
	ArrayList v = new ArrayList();
	
	v.Add(new int[]{5, 4});
	v.Add(new int[]{5, 8});
	v.Add(new int[]{4, 6});
	v.Add(new int[]{4, 9});
	v.Add(new int[]{8, 10});
	v.Add(new int[]{10, 20});
	v.Add(new int[]{10, 30});
	
	Console.Write(max_gcd(v));
}
}

Output:

Example 3

// Writing a Java program to determine the maximum GCD of the siblings in the array.  
import java.util.*;
import java.lang.*;


class TFT{
// writing a function to find the maximum GCD
static int max_gcd(ArrayList<int[]> v)
{
// If there is no child or a single child
	if (v.size() == 1 || v.size() == 0)
		return 0;


	Collections.sort(v, new Comparator<int[]>() {
		public int compare(int[] a, int[] b) {
			return a[0]-b[0];
		}
	});
	// now, we have to find the first pair
	int[] a = v.get(0);
	int[] b = new int[2];
	int ans = Integer.MIN_VALUE;
	
	for(int i = 1; i < v.size(); i++)
	{
		b = v.get(i);
	// Suppose both the pairs of the node belong to the same node or the parent node. 		
		if (b[0] == a[0])
// Now we will begin by updating the ans with the maximum of the current and gcd of both children. 
			ans = Math.max(ans,
						gcd(a[1],
							b[1]));
		// now we will begin by updating the next iteration
		a = b;
	}
	return ans;
}


static int gcd(int a, int b)
{
	if (b == 0)
		return a;
		
	return gcd(b, a % b);
}
// writing the main code to test the above program.	
public static void main(String[] args)
{
	ArrayList<int[]> v = new ArrayList<>();
	
	v.add(new int[]{5, 4});
	v.add(new int[]{5, 8});
	v.add(new int[]{4, 6});
	v.add(new int[]{4, 9});
	v.add(new int[]{8, 10});
	v.add(new int[]{10, 20});
	v.add(new int[]{10, 30});
	
	System.out.println(max_gcd(v));
}
}

Output:

Example 4

# Writing a Python program to find out the maximum GCD of the siblings that are present in an array.  
from math import gcd


# writing a function to find the maximum GCD
def max_gcd(v):
# If there is no child or a single child
	if (len(v) == 1 or len(v) == 0):
		return 0
	
	v.sort()
	# now we have to find the first pair
	a = v[0]
	ans = -10**9
	for i in range(1, len(v)):
		b = v[i]
# Suppose both the pairs of the node belong to the same node or the parent node. 
		if (b[0] == a[0]):


		# Now, we will begin by updating the ans with the maximum of the children's current gcd and the gcd. 
			ans = max(ans, gcd(a[1], b[1]))


# now, we will begin by updating the next iteration
		a = b
	return ans
# writing the main code to test the above program
if __name__ == '__main__':
	v=[]
	v.append([5, 4])
	v.append([5, 8])
	v.append([4, 6])
	v.append([4, 9])
	v.append([8, 10])
	v.append([10, 20])
	v.append([10, 30])


	print(max_gcd(v))

Output: