Dado un Árbol Binario , la tarea es imprimir el conteo de Nodes cuyo hijo inmediato sea su factor primo .
Ejemplos:
Input:
1
/ \
15 20
/ \ / \
3 5 4 2
\ /
2 3
Output: 3
Explanation:
Children of 15 (3, 5)
are prime factors of 15
Child of 20 (2)
is prime factors of 20
Child of 4 (2)
is prime factors of 4
Input:
7
/ \
210 14
/ \ \
70 14 30
/ \ / \
2 5 3 5
/
23
Output: 2
Explanation:
Children of 70 (2, 5)
are prime factors of 70
Children of 30 (3, 5)
are prime factors of 30
Acercarse:
- Atraviese el árbol binario dado y para cada Node:
- Comprobar si existen niños o no.
- Si los hijos existen, verifique si cada hijo es un factor primo de este Node o no.
- Lleve la cuenta de dichos Nodes e imprímalo al final.
- Para verificar si un factor es primo, usaremos la criba de Eratóstenes para precalcular los números primos para hacer la verificación en O(1).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Counting nodes whose
// immediate children are its factors
#include <bits/stdc++.h>
using namespace std;
int N = 1000000;
// To store all prime numbers
vector<int> prime;
void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..N]"
// and initialize all its entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime, else true.
bool check[N + 1];
memset(check, true, sizeof(check));
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (check[p] == true) {
prime.push_back(p);
// Update all multiples of p
// greater than or equal to
// the square of it
// numbers which are multiples of p
// and are less than p^2
// are already marked.
for (int i = p * p; i <= N; i += p)
check[i] = false;
}
}
}
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to check if immediate children
// of a node are its factors or not
bool IsChilrenPrimeFactor(struct Node* parent,
struct Node* a)
{
if (prime[a->key]
&& (parent->key % a->key == 0))
return true;
else
return false;
}
// Function to get the count of full Nodes in
// a binary tree
unsigned int GetCount(struct Node* node)
{
// If tree is empty
if (!node)
return 0;
queue<Node*> q;
// Do level order traversal starting
// from root
// Initialize count of full nodes having
// children as their factors
int count = 0;
q.push(node);
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
// If only right child exist
if (temp->left == NULL
&& temp->right != NULL) {
if (IsChilrenPrimeFactor(
temp,
temp->right))
count++;
}
else {
// If only left child exist
if (temp->right == NULL
&& temp->left != NULL) {
if (IsChilrenPrimeFactor(
temp,
temp->left))
count++;
}
else {
// Both left and right child exist
if (temp->left != NULL
&& temp->right != NULL) {
if (IsChilrenPrimeFactor(
temp,
temp->right)
&& IsChilrenPrimeFactor(
temp,
temp->left))
count++;
}
}
}
// Check for left child
if (temp->left != NULL)
q.push(temp->left);
// Check for right child
if (temp->right != NULL)
q.push(temp->right);
}
return count;
}
// Driver Code
int main()
{
/* 10
/ \
2 5
/ \
18 12
/ \ / \
2 3 3 14
/
7
*/
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(2);
root->right = newNode(5);
root->right->left = newNode(18);
root->right->right = newNode(12);
root->right->left->left = newNode(2);
root->right->left->right = newNode(3);
root->right->right->left = newNode(3);
root->right->right->right = newNode(14);
root->right->right->right->left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Count of all nodes having children
// as their factors
cout << GetCount(root) << endl;
return 0;
}
Java
// Java program for Counting nodes whose
// immediate children are its factors
import java.util.*;
class GFG{
static int N = 1000000;
// To store all prime numbers
static Vector<Integer> prime = new Vector<Integer>();
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..N]"
// and initialize all its entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime, else true.
boolean []check = new boolean[N + 1];
Arrays.fill(check, true);
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (check[p] == true) {
prime.add(p);
// Update all multiples of p
// greater than or equal to
// the square of it
// numbers which are multiples of p
// and are less than p^2
// are already marked.
for (int i = p * p; i <= N; i += p)
check[i] = false;
}
}
}
// A Tree node
static class Node {
int key;
Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to check if immediate children
// of a node are its factors or not
static boolean IsChilrenPrimeFactor(Node parent,
Node a)
{
if (prime.get(a.key)>0
&& (parent.key % a.key == 0))
return true;
else
return false;
}
// Function to get the count of full Nodes in
// a binary tree
static int GetCount(Node node)
{
// If tree is empty
if (node == null)
return 0;
Queue<Node> q = new LinkedList<>();
// Do level order traversal starting
// from root
// Initialize count of full nodes having
// children as their factors
int count = 0;
q.add(node);
while (!q.isEmpty()) {
Node temp = q.peek();
q.remove();
// If only right child exist
if (temp.left == null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right))
count++;
}
else {
// If only left child exist
if (temp.right == null
&& temp.left != null) {
if (IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
else {
// Both left and right child exist
if (temp.left != null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right)
&& IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
}
}
// Check for left child
if (temp.left != null)
q.add(temp.left);
// Check for right child
if (temp.right != null)
q.add(temp.right);
}
return count;
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
2 5
/ \
18 12
/ \ / \
2 3 3 14
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(5);
root.right.left = newNode(18);
root.right.right = newNode(12);
root.right.left.left = newNode(2);
root.right.left.right = newNode(3);
root.right.right.left = newNode(3);
root.right.right.right = newNode(14);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Count of all nodes having children
// as their factors
System.out.print(GetCount(root) +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program for Counting nodes whose # immediate children are its factors from collections import deque N = 1000000 # To store all prime numbers prime = [] def SieveOfEratosthenes() -> None: # Create a boolean array "prime[0..N]" # and initialize all its entries as true. # A value in prime[i] will finally # be false if i is Not a prime, else true. check = [True for _ in range(N + 1)] p = 2 while p * p <= N: # If prime[p] is not changed, # then it is a prime if (check[p]): prime.append(p) # Update all multiples of p # greater than or equal to # the square of it # numbers which are multiples of p # and are less than p^2 # are already marked. for i in range(p * p, N + 1, p): check[i] = False p += 1 # A Tree node class Node: def __init__(self, key: int) -> None: self.key = key self.left = None self.right = None # Function to check if immediate children # of a node are its factors or not def IsChilrenPrimeFactor(parent: Node, a: Node) -> bool: if (prime[a.key] and (parent.key % a.key == 0)): return True else: return False # Function to get the count of full Nodes in # a binary tree def GetCount(node: Node) -> int: # If tree is empty if (not node): return 0 q = deque() # Do level order traversal starting # from root # Initialize count of full nodes having # children as their factors count = 0 q.append(node) while q: temp = q.popleft() # If only right child exist if (temp.left == None and temp.right != None): if (IsChilrenPrimeFactor(temp, temp.right)): count += 1 else: # If only left child exist if (temp.right == None and temp.left != None): if (IsChilrenPrimeFactor(temp, temp.left)): count += 1 else: # Both left and right child exist if (temp.left != None and temp.right != None): if (IsChilrenPrimeFactor(temp, temp.right) and IsChilrenPrimeFactor(temp, temp.left)): count += 1 # Check for left child if (temp.left != None): q.append(temp.left) # Check for right child if (temp.right != None): q.append(temp.right) return count # Driver Code if __name__ == "__main__": ''' 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 14 / 7 ''' # Create Binary Tree as shown root = Node(10) root.left = Node(2) root.right = Node(5) root.right.left = Node(18) root.right.right = Node(12) root.right.left.left = Node(2) root.right.left.right = Node(3) root.right.right.left = Node(3) root.right.right.right = Node(14) root.right.right.right.left = Node(7) # To save all prime numbers SieveOfEratosthenes() # Print Count of all nodes having children # as their factors print(GetCount(root)) # This code is contributed by sanjeev2552
C#
// C# program for Counting nodes whose
// immediate children are its factors
using System;
using System.Collections.Generic;
public class GFG{
static int N = 1000000;
// To store all prime numbers
static List<int> prime = new List<int>();
static void SieveOfEratosthenes()
{
// Create a bool array "prime[0..N]"
// and initialize all its entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime, else true.
bool []check = new bool[N + 1];
for (int i = 0; i <= N; i += 1)
check[i] = true;
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (check[p] == true) {
prime.Add(p);
// Update all multiples of p
// greater than or equal to
// the square of it
// numbers which are multiples of p
// and are less than p^2
// are already marked.
for (int i = p * p; i <= N; i += p)
check[i] = false;
}
}
}
// A Tree node
class Node {
public int key;
public Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to check if immediate children
// of a node are its factors or not
static bool IsChilrenPrimeFactor(Node parent,
Node a)
{
if (prime[a.key]>0
&& (parent.key % a.key == 0))
return true;
else
return false;
}
// Function to get the count of full Nodes in
// a binary tree
static int GetCount(Node node)
{
// If tree is empty
if (node == null)
return 0;
List<Node> q = new List<Node>();
// Do level order traversal starting
// from root
// Initialize count of full nodes having
// children as their factors
int count = 0;
q.Add(node);
while (q.Count!=0) {
Node temp = q[0];
q.RemoveAt(0);
// If only right child exist
if (temp.left == null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right))
count++;
}
else {
// If only left child exist
if (temp.right == null
&& temp.left != null) {
if (IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
else {
// Both left and right child exist
if (temp.left != null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right)
&& IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
}
}
// Check for left child
if (temp.left != null)
q.Add(temp.left);
// Check for right child
if (temp.right != null)
q.Add(temp.right);
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
/* 10
/ \
2 5
/ \
18 12
/ \ / \
2 3 3 14
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(2);
root.right = newNode(5);
root.right.left = newNode(18);
root.right.right = newNode(12);
root.right.left.left = newNode(2);
root.right.left.right = newNode(3);
root.right.right.left = newNode(3);
root.right.right.right = newNode(14);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Count of all nodes having children
// as their factors
Console.Write(GetCount(root) +"\n");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for Counting nodes whose
// immediate children are its factors
let N = 1000000;
// To store all prime numbers
let prime = [];
function SieveOfEratosthenes()
{
// Create a boolean array "prime[0..N]"
// and initialize all its entries as true.
// A value in prime[i] will finally
// be false if i is Not a prime, else true.
let check = new Array(N + 1);
check.fill(true);
for (let p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (check[p] == true) {
prime.push(p);
// Update all multiples of p
// greater than or equal to
// the square of it
// numbers which are multiples of p
// and are less than p^2
// are already marked.
for (let i = p * p; i <= N; i += p)
check[i] = false;
}
}
}
// A Tree node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Function to check if immediate children
// of a node are its factors or not
function IsChilrenPrimeFactor(parent, a)
{
if (prime[a.key]>0
&& (parent.key % a.key == 0))
return true;
else
return false;
}
// Function to get the count of full Nodes in
// a binary tree
function GetCount(node)
{
// If tree is empty
if (node == null)
return 0;
let q = [];
// Do level order traversal starting
// from root
// Initialize count of full nodes having
// children as their factors
let count = 0;
q.push(node);
while (q.length > 0) {
let temp = q[0];
q.shift();
// If only right child exist
if (temp.left == null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right))
count++;
}
else {
// If only left child exist
if (temp.right == null
&& temp.left != null) {
if (IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
else {
// Both left and right child exist
if (temp.left != null
&& temp.right != null) {
if (IsChilrenPrimeFactor(
temp,
temp.right)
&& IsChilrenPrimeFactor(
temp,
temp.left))
count++;
}
}
}
// Check for left child
if (temp.left != null)
q.push(temp.left);
// Check for right child
if (temp.right != null)
q.push(temp.right);
}
return count;
}
/* 10
/ \
2 5
/ \
18 12
/ \ / \
2 3 3 14
/
7
*/
// Create Binary Tree as shown
let root = newNode(10);
root.left = newNode(2);
root.right = newNode(5);
root.right.left = newNode(18);
root.right.right = newNode(12);
root.right.left.left = newNode(2);
root.right.left.right = newNode(3);
root.right.right.left = newNode(3);
root.right.right.right = newNode(14);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Count of all nodes having children
// as their factors
document.write(GetCount(root) +"</br>");
</script>
Producción:
3
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 bfs es O(N) si hay un total de N Nodes en el árbol. Además, para procesar cada Node, se utiliza la función SieveOfEratosthenes(), que también tiene una complejidad de O(sqrt(N)), pero dado que esta función se ejecuta solo una vez, no afecta la complejidad temporal general. Por lo tanto, la complejidad del tiempo es O(N). - Espacio Auxiliar : O(N).
Se utiliza espacio adicional para la array principal, por lo que la complejidad del espacio es O(N).