Given an N-ary tree and an array val[] which stores the values associated with all the nodes. Also given are a leaf node X and N integers which denotes the value of the node. The task is to find the gcd of all the numbers in the node in the path between leaf to the root.
Examples:
Input:
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
val[] = { -1, 6, 2, 6, 3, 4, 12, 10, 18 }
leaf = 8
Output: 6
GCD(val[1], val[3], val[6], val[8]) = GCD(6, 6, 12, 18) = 6
Input:
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
val[] = { 6, 2, 6, 3, 4, 12, 10, 18 }
leaf = 5
Output: 2
Approach: The problem can be solved using DFS in a tree. In the DFS function, we include an extra parameter G with the initial value as the root. Every time we visit a new node by calling DFS function recursively, we update the value of G to gcd(G, val[node]) . Once we reach the given leaf node, we print the value of gcd(G, val[leaf-node]) and break out of DFS function.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 9// Function to add edges in the treevoid addEgde(list<int>* adj, int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Function to find the GCD from root to leaf pathvoid DFS(int node, int parent, int G, int leaf, int val[], list<int>* adj){ // If we reach the desired leaf if (node == leaf) { G = __gcd(G, val[node]); cout << G; return; } // Call DFS for children for (auto it : adj[node]) { if (it != parent) DFS(it, node, __gcd(G, val[it]), leaf, val, adj); }}// Driver codeint main(){ int n = 8; list<int>* adj = new list<int>[n + 1]; addEgde(adj, 1, 2); addEgde(adj, 2, 4); addEgde(adj, 1, 3); addEgde(adj, 3, 5); addEgde(adj, 3, 6); addEgde(adj, 6, 7); addEgde(adj, 6, 8); int leaf = 5; // -1 to indicate no value in node 0 int val[] = { -1, 6, 2, 6, 3, 4, 12, 10, 18 }; // Initially GCD is the value of the root int G = val[1]; DFS(1, -1, G, leaf, val, adj); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static final int N = 9;// Function to add edges in the treestatic void addEgde(List<Integer> []adj, int u, int v){ adj[u].add(v); adj[v].add(u);}// Function to find the GCD from root to leaf pathstatic void DFS(int node, int parent, int G, int leaf, int val[], List<Integer> []adj){ // If we reach the desired leaf if (node == leaf) { G = __gcd(G, val[node]); System.out.print(G); return; } // Call DFS for children for (int it : adj[node]) { if (it != parent) DFS(it, node, __gcd(G, val[it]), leaf, val, adj); }}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }// Driver codepublic static void main(String[] args){ int n = 8; List<Integer> []adj = new LinkedList[n + 1]; for (int i = 0; i < n + 1; i++) adj[i] = new LinkedList<Integer>(); addEgde(adj, 1, 2); addEgde(adj, 2, 4); addEgde(adj, 1, 3); addEgde(adj, 3, 5); addEgde(adj, 3, 6); addEgde(adj, 6, 7); addEgde(adj, 6, 8); int leaf = 5; // -1 to indicate no value in node 0 int val[] = { -1, 6, 2, 6, 3, 4, 12, 10, 18 }; // Initially GCD is the value of the root int G = val[1]; DFS(1, -1, G, leaf, val, adj);}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 implementation of the approachfrom math import gcdN = 9# Function to add edges in the treedef addEgde(adj, u, v): adj[u].append(v) adj[v].append(u)# Function to find the GCD # from root to leaf pathdef DFS(node, parent, G, leaf, val, adj): # If we reach the desired leaf if (node == leaf): G = gcd(G, val[node]) print(G, end = "") return # Call DFS for children for it in adj[node]: if (it != parent): DFS(it, node, gcd(G, val[it]), leaf, val, adj)# Driver codeif __name__ == '__main__': n = 8 adj = [[0 for i in range(n + 1)] for j in range(n + 1)] addEgde(adj, 1, 2) addEgde(adj, 2, 4) addEgde(adj, 1, 3) addEgde(adj, 3, 5) addEgde(adj, 3, 6) addEgde(adj, 6, 7) addEgde(adj, 6, 8) leaf = 5 # -1 to indicate no value in node 0 val = [-1, 6, 2, 6, 3, 4, 12, 10, 18] # Initially GCD is the value of the root G = val[1] DFS(1, -1, G, leaf, val, adj)# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static readonly int N = 9; // Function to add edges in the treestatic void addEgde(List<int> []adj, int u, int v){ adj[u].Add(v); adj[v].Add(u);} // Function to find the GCD from root to leaf pathstatic void DFS(int node, int parent, int G, int leaf, int []val, List<int> []adj){ // If we reach the desired leaf if (node == leaf) { G = __gcd(G, val[node]); Console.Write(G); return; } // Call DFS for children foreach (int it in adj[node]) { if (it != parent) DFS(it, node, __gcd(G, val[it]), leaf, val, adj); }}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } // Driver codepublic static void Main(String[] args){ int n = 8; List<int> []adj = new List<int>[n + 1]; for (int i = 0; i < n + 1; i++) adj[i] = new List<int>(); addEgde(adj, 1, 2); addEgde(adj, 2, 4); addEgde(adj, 1, 3); addEgde(adj, 3, 5); addEgde(adj, 3, 6); addEgde(adj, 6, 7); addEgde(adj, 6, 8); int leaf = 5; // -1 to indicate no value in node 0 int []val = { -1, 6, 2, 6, 3, 4, 12, 10, 18 }; // Initially GCD is the value of the root int G = val[1]; DFS(1, -1, G, leaf, val, adj);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approachlet N = 9;// Function to add edges in the treefunction addEgde(adj,u,v){ adj[u].push(v); adj[v].push(u);}// Function to find the GCD from root to leaf pathfunction DFS(node,parent,G,leaf,val,adj){ // If we reach the desired leaf if (node == leaf) { G = __gcd(G, val[node]); document.write(G); return; } // Call DFS for children for (let it of adj[node]) { if (it != parent) DFS(it, node, __gcd(G, val[it]), leaf, val, adj); }}// Driver codefunction __gcd(a,b){ return b == 0? a:__gcd(b, a % b); }let n = 8;let adj = new Array(n + 1);for (let i = 0; i < n + 1; i++) adj[i] = [];addEgde(adj, 1, 2);addEgde(adj, 2, 4);addEgde(adj, 1, 3);addEgde(adj, 3, 5);addEgde(adj, 3, 6);addEgde(adj, 6, 7);addEgde(adj, 6, 8);let leaf = 5;// -1 to indicate no value in node 0let val = [ -1, 6, 2, 6, 3, 4, 12, 10, 18 ];// Initially GCD is the value of the rootlet G = val[1];DFS(1, -1, G, leaf, val, adj);// This code is contributed by rag2127</script> |
Output:
2
Time Complexity: O(NlogN), as we are traversing the graph using DFS (recursion). Where N is the number of nodes in the graph.
Auxiliary Space: O(N), as we are using extra space for the recursive stack. Where N is the number of nodes in the graph.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
