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 Poderoso .
Un número n se dice Número Poderoso si, para todo factor primo p de él, p 2 también lo divide.
Ejemplo:
Aporte:
Resultado: 3
Explicación:
4, 16 y 25 son pesos poderosos en el árbol.
Enfoque: para resolver el problema mencionado anteriormente, tenemos que realizar una búsqueda en profundidad (DFS) en el árbol y, para cada Node, verificar si su peso es un número poderoso o no. Si es así, entonces incremente el conteo.
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 powerful number
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
vector<int> graph[100];
vector<int> weight(100);
// Function to check if the number is powerful
bool isPowerful(int n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
for (int factor = 3; factor <= sqrt(n); factor += 2) {
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// Check if only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to perform dfs
void dfs(int node, int parent)
{
// Check if weight of the current node
// is a powerful number
if (isPowerful(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 powerful number
import java.util.*;
class GFG {
static int ans = 0;
static Vector<Integer>[] graph = new Vector[100];
static int[] weight = new int[100];
// Function to check if the number is powerful
static boolean isPowerful(int n) {
// First divide the number repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
for (int factor = 3; factor <= Math.sqrt(n); factor += 2) {
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// Check if only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to perform dfs
static void dfs(int node, int parent) {
// Check if weight of the current node
// is a powerful number
if (isPowerful(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 is contributed by Princi Singh
Python3
# Python3 implementation to # Count the Nodes in the given # tree whose weight is a powerful # number graph = [[] for i in range(100)] weight = [0] * 100 ans = 0 # Function to check if the # number is powerful def isPowerful(n): # First divide the number # repeatedly by 2 while (n % 2 == 0): power = 0; while (n % 2 == 0): n /= 2; power += 1; # Check if only 2^1 # divides n, then # return False if (power == 1): return False; # Check if n is not a # power of 2 then this # loop will execute factor = 3 while(factor *factor <=n): # Find highest power of # "factor" that divides n power = 0; while (n % factor == 0): n = n / factor; power += 1; # Check if only factor^1 # divides n, then return # False if (power == 1): return False; factor +=2; # n must be 1 now # if it is not a prime # number. Since prime # numbers are not powerful, # we return False if n is # not 1. return (n == 1); # Function to perform dfs def dfs(Node, parent): # Check if weight of # the current Node # is a powerful number global ans; if (isPowerful(weight[Node])): ans += 1; for to in graph[Node]: if (to == parent): continue; dfs(to, Node); # Driver code if __name__ == '__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); dfs(1, 1); print(ans); # This code is contributed by 29AjayKumar
C#
// C# implementation to count the
// nodes in thegiven tree whose weight
// is a powerful 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 to check if the number
// is powerful
static bool isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
for(int factor = 3;
factor <= Math.Sqrt(n);
factor += 2)
{
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// Check if only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to perform dfs
static void dfs(int node, int parent)
{
// Check if weight of the current node
// is a powerful number
if (isPowerful(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 powerful number
var ans = 0;
var graph = Array.from(Array(100), ()=>Array());
var weight = Array.from(Array(100), ()=>Array());
// Function to check if the number is powerful
function isPowerful(n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0) {
var power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
for (var factor = 3; factor <= Math.sqrt(n); factor += 2) {
// Find highest power of "factor"
// that divides n
var power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// Check if only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers are not powerful,
// we return false if n is not 1.
return (n == 1);
}
// Function to perform dfs
function dfs(node, parent)
{
// Check if weight of the current node
// is a powerful number
if (isPowerful(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>
Producción:
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 a dfs es O(N) si hay un total de N Nodes en el árbol. Además, al procesar cada Node, para verificar si el valor del Node es un número poderoso o no, se llama a la función isPowerful (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