Dado un árbol N-ario y una array val[] que almacena los valores asociados con todos los Nodes. También se dan un Node de hoja X y N enteros que denotan el valor del Node. La tarea es encontrar el mcd de todos los números en el Node en el camino entre la hoja y la raíz.
Ejemplos:
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
Enfoque: El problema se puede resolver usando DFS en un árbol . En la función DFS, incluimos un parámetro adicional G con el valor inicial como raíz. Cada vez que visitamos un nuevo Node llamando recursivamente a la función DFS, actualizamos el valor de G a gcd (G, val[node]) . Una vez que llegamos al Node hoja dado, imprimimos el valor de gcd(G, val[Node-hoja]) y salimos de la función DFS.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 9
// Function to add edges in the tree
void 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 path
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]);
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 code
int 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 approach
import java.util.*;
class GFG
{
static final int N = 9;
// Function to add edges in the tree
static 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 path
static 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 code
public 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 approach from math import gcd N = 9 # Function to add edges in the tree def addEgde(adj, u, v): adj[u].append(v) adj[v].append(u) # Function to find the GCD # from root to leaf path def 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 code if __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 approach
using System;
using System.Collections.Generic;
class GFG
{
static readonly int N = 9;
// Function to add edges in the tree
static 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 path
static 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 code
public 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 approach
let N = 9;
// Function to add edges in the tree
function addEgde(adj,u,v)
{
adj[u].push(v);
adj[v].push(u);
}
// Function to find the GCD from root to leaf path
function 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 code
function __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 0
let val = [ -1, 6, 2, 6, 3, 4, 12, 10, 18 ];
// Initially GCD is the value of the root
let G = val[1];
DFS(1, -1, G, leaf, val, adj);
// This code is contributed by rag2127
</script>
Producción:
2
Complejidad de tiempo: O (NlogN), ya que estamos atravesando el gráfico usando DFS (recursión). Donde N es el número de Nodes en el gráfico.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la pila recursiva. Donde N es el número de Nodes en el gráfico.