Dado un árbol con los pesos de todos los Nodes, la tarea es encontrar el Node de peso máximo cuyo peso tiene una suma de dígitos pares.
Ejemplos:
Input: Tree =
5
/ \
10 6
/ \
11 8
Output: 11
Explanation:
The tree node weights are:
5 -> 5
10 -> 1 + 0 = 1
6 -> 6
11 -> 1 + 1 = 2
8 -> 8
Here, digit sum for nodes
containing 11, 6 and 8 are even.
Hence, the maximum weighing
even digit sum node is 11.
Input: Tree =
1
/ \
4 7
/ \ / \
11 3 15 8
Output: 15
Explanation:
Here, digit sum for nodes containing
4, 11, 15 and 8 are even.
Hence, the maximum weighing
even digit sum node is 15.
Enfoque: Para resolver el problema mencionado anteriormente, siga los pasos que se detallan a continuación:
- La idea es realizar una primera búsqueda en profundidad en el árbol y para cada Node.
- Primero, encuentre la suma de dígitos para el peso presente en el Node iterando a través de cada dígito y luego verifique si el Node tiene una suma de dígitos pares o no.
- Finalmente, si tiene una suma de dígitos pares, verifique si este Node es el Node de suma de dígitos pares máximo que hemos encontrado hasta ahora, en caso afirmativo, haga que este Node sea el Node de suma de dígitos pares máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// maximum weighing node
// in the tree whose weight
// has an Even Digit Sum
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
int ans = -1;
vector<int> graph[100];
vector<int> weight(100);
// Function to find the digit sum
// for a number
int digitSum(int num)
{
int sum = 0;
while (num)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to perform dfs
void dfs(int node, int parent)
{
// Check if the digit sum
// of the node weight
// is even or not
if (!(digitSum(weight[node]) & 1))
ans = max(ans, weight[node]);
// Performing DFS to iterate the
// remaining nodes
for (int to : graph[node]) {
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
int main()
{
// Weights of the node
weight[1] = 5;
weight[2] = 10;
weight[3] = 11;
weight[4] = 8;
weight[5] = 6;
// Edges of the tree
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[1].push_back(5);
// Call the dfs function to
// traverse through the tree
dfs(1, 1);
cout << ans << endl;
return 0;
}
Java
// Java program to find the
// maximum weighing node
// in the tree whose weight
// has an Even Digit Sum
import java.util.*;
class GFG
{
static int sz = (int)1e5;
static int ans = -1;
static Vector<Integer>[] graph = new Vector[100];
static int[] weight = new int[100];
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// Check if the digit sum
// of the node weight
// is even or not
if (!(digitSum(weight[node]) % 2 == 1))
ans = Math.max(ans, weight[node]);
// Performing DFS to iterate the
// remaining nodes
for (int to : graph[node])
{
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
public static void main(String[] args)
{
// Weights of the node
weight[1] = 5;
weight[2] = 10;
weight[3] = 11;
weight[4] = 8;
weight[5] = 6;
for (int i = 0; i < graph.length; i++)
graph[i] = new Vector<Integer>();
// Edges of the tree
graph[1].add(2);
graph[2].add(3);
graph[2].add(4);
graph[1].add(5);
// Call the dfs function to
// traverse through the tree
dfs(1, 1);
System.out.print(ans + "\n");
}
}
// This code contributed by Princi Singh
Python3
# Python3 program to find the # maximum weighing node # in the tree whose weight # has an Even Digit Sum sz = 1e5 ans = -1 graph = [[] for i in range(100)] weight = [-1] * 100 # Function to find the digit sum # for a number def digitSum(num): sum = 0 while num: sum += num % 10 num = num // 10 return sum # Function to perform dfs def dfs(node, parent): global ans # Check if the digit sum # of the node weight # is even or not if not(digitSum(weight[node]) & 1): ans = max(ans, weight[node]) # Performing DFS to iterate the # remaining nodes for to in graph[node]: if to == parent: continue dfs(to, node) # Driver code def main(): # Weights of the node weight[1] = 5 weight[2] = 10 weight[3] = 11 weight[4] = 8 weight[5] = 6 # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) # Call the dfs function to # traverse through the tree dfs(1, 1) print(ans) main() # This code is contributed by stutipathak31jan
C#
// C# program to find the
// maximum weighing node
// in the tree whose weight
// has an Even Digit Sum
using System;
using System.Collections.Generic;
class GFG
{
static int sz = (int)1e5;
static int ans = -1;
static List<int>[] graph = new List<int>[ 100 ];
static int[] weight = new int[100];
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// Check if the digit sum
// of the node weight
// is even or not
if (!(digitSum(weight[node]) % 2 == 1))
ans = Math.Max(ans, weight[node]);
// Performing DFS to iterate the
// remaining nodes
foreach(int to in graph[node])
{
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
public static void Main(String[] args)
{
// Weights of the node
weight[1] = 5;
weight[2] = 10;
weight[3] = 11;
weight[4] = 8;
weight[5] = 6;
for (int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Edges of the tree
graph[1].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
// Call the dfs function to
// traverse through the tree
dfs(1, 1);
Console.Write(ans + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the
// maximum weighing node
// in the tree whose weight
// has an Even Digit Sum
let sz = 1e5;
let ans = -1;
let graph = new Array(100);
let weight = new Array(100);
// Function to find the digit sum
// for a number
function digitSum(num)
{
let sum = 0;
while (num > 0)
{
sum += (num % 10);
num = parseInt(num / 10, 10);
}
return sum;
}
// Function to perform dfs
function dfs(node, parent)
{
// Check if the digit sum
// of the node weight
// is even or not
if (!(digitSum(weight[node]) % 2 == 1))
ans = Math.max(ans, weight[node]);
// Performing DFS to iterate the
// remaining nodes
for (let to = 0; to < graph[node].length; to++)
{
if (graph[node][to] == parent)
continue;
dfs(graph[node][to], node);
}
}
// Weights of the node
weight[1] = 5;
weight[2] = 10;
weight[3] = 11;
weight[4] = 8;
weight[5] = 6;
for (let i = 0; i < graph.length; i++)
graph[i] = [];
// Edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
// Call the dfs function to
// traverse through the tree
dfs(1, 1);
document.write(ans + "</br>");
// This code is contributed by decode2207.
</script>
Producción
11
Análisis de Complejidad:
Complejidad temporal: O(N).
En dfs, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida a dfs es O(N) si hay un total de N Nodes en el árbol. Además, para procesar cada Node se usa la función DigitSum() que tiene una complejidad de O(d), donde d es el número de dígitos en el peso de un Node, sin embargo, dado que el peso de cualquier Node es un número entero, puede solo tiene 10 dígitos como máximo, por lo tanto, esta función no afecta la complejidad del tiempo general. Por lo tanto, la complejidad del tiempo es O(N).
Espacio Auxiliar : O(1).
No se requiere ningún espacio adicional, por lo que la complejidad del espacio es constante.
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA