Dado un árbol y los pesos de todos los Nodes, la tarea es contar el número de Nodes cuyo peso es un número perfecto .
Un número perfecto es un entero positivo que es igual a la suma de sus divisores propios .
Ejemplos:
Aporte:
Salida: 0
Explicación:
No hay ningún Node con un peso que sea un número perfecto.
Enfoque:
para resolver este problema, realizamos un recorrido transversal de búsqueda en profundidad (DFS) en el árbol y, para cada Node, verificamos si su peso es un número perfecto o no . Seguimos incrementando el contador cada vez que se obtiene tal peso. El valor final de ese contador después de completar todo el recorrido del árbol es la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Count the nodes in the
// given tree whose weight is a Perfect Number
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
vector<int> graph[100];
vector<int> weight(100);
// Function that returns true if n is perfect
bool isPerfect(long long int n)
{
// Variable to store sum of divisors
long long int sum = 1;
// Find all divisors and add them
for (long long int i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to perform dfs
void dfs(int node, int parent)
{
// If weight of the current node
// is a perfect number
if (isPerfect(weight[node]))
ans += 1;
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);
dfs(1, 1);
cout << ans;
return 0;
}
Java
// Java implementation to Count the nodes in the
// given tree whose weight is a Perfect Number
import java.util.*;
class GFG{
static int ans = 0;
static Vector<Integer> []graph = new Vector[100];
static int []weight = new int[100];
// Function that returns true if n is perfect
static boolean isPerfect(int n)
{
// Variable to store sum of divisors
int sum = 1;
// Find all divisors and add them
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// If weight of the current node
// is a perfect number
if (isPerfect(weight[node]))
ans += 1;
for (int to : graph[node]) {
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
public static void main(String[] args)
{
for (int i = 0; i < graph.length; i++)
graph[i] = new Vector<Integer>();
// 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].add(2);
graph[2].add(3);
graph[2].add(4);
graph[1].add(5);
dfs(1, 1);
System.out.print(ans);
}
}
// This code contributed by Princi Singh
Python3
# Python3 implementation to # Count the Nodes in the given # tree whose weight is a Perfect # Number graph = [[] for i in range(100)] weight = [0] * 100 ans = 0 # Function that returns # True if n is perfect def isPerfect(n): # Variable to store # sum of divisors sum = 1; # Find all divisors # and add them i = 2; while(i * i < n): if (n % i == 0): if (i * i != n): sum = sum + i + n / i; else: sum = sum + i; i += 1; # Check if sum of divisors # is equal to n, then n is # a perfect number if (sum == n and n != 1): return True; return False; # Function to perform dfs def dfs(Node, parent): # If weight of the current # Node is a perfect number global ans; if (isPerfect(weight[Node])): ans += 1; for to in graph[Node]: if (to == parent): continue; dfs(to, Node); # Driver code # 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); dfs(1, 1); print(ans); # This code is contributed by 29AjayKumar
C#
// C# implementation to count the
// nodes in the given tree whose
// weight is a Perfect Number
using System;
using System.Collections.Generic;
class GFG{
static int ans = 0;
static List<int> []graph = new List<int>[100];
static int []weight = new int[100];
// Function that returns true
// if n is perfect
static bool isPerfect(int n)
{
// Variable to store sum of
// divisors
int sum = 1;
// Find all divisors and add them
for(int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal
// to n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// If weight of the current node
// is a perfect number
if (isPerfect(weight[node]))
ans += 1;
foreach(int to in graph[node])
{
if (to == parent)
continue;
dfs(to, node);
}
}
// Driver code
public static void Main(String[] args)
{
for(int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// 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].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
dfs(1, 1);
Console.Write(ans);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript implementation to Count the nodes in the
// given tree whose weight is a Perfect Number
var ans = 0;
var graph = Array.from(Array(100), ()=>Array());
var weight = Array.from(Array(100), ()=>Array());
// Function that returns true if n is perfect
function isPerfect(n)
{
// Variable to store sum of divisors
var sum = 1;
// Find all divisors and add them
for (var i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to perform dfs
function dfs( node, parent)
{
// If weight of the current node
// is a perfect number
if (isPerfect(weight[node]))
ans += 1;
graph[node].forEach(to => {
if (to != parent)
dfs(to, node);
});
}
// Driver code
// 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(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
dfs(1, 1);
document.write( ans);
</script>
1
Análisis de Complejidad:
Complejidad temporal : O(N*logV), donde V es el peso máximo de un Node en el árbol
En DFS, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida al dfs es O(N) si hay un total de N Nodes en el árbol. Además, al procesar cada Node, para comprobar si el valor del Node es un número perfecto o no, se llama a la función isPerfect(V) donde V es el peso del Node y esta función tiene una complejidad de O(logV) , por lo tanto, para cada Node, hay una complejidad adicional de O (logV). Por lo tanto, la complejidad del tiempo es O(N*logV).
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 saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA