Dado un Árbol Binario , la tarea es imprimir todos los niveles Co-prime de este árbol.
Se dice que cualquier nivel de un árbol binario es un nivel coprimo si todos los Nodes de este nivel son coprimos entre sí.
Ejemplos:
Input:
1
/ \
15 5
/ / \
11 4 15
\ /
2 3
Output:
1
11 4 15
2 3
Explanation:
First, Third and Fourth levels
are co-prime levels.
Input:
7
/ \
21 14
/ \ \
77 16 3
/ \ \ /
2 5 10 11
/
23
Output:
7
77 16 3
23
Explanation:
First, Third and Fifth levels
are co-prime levels.
Enfoque: Para verificar si un nivel es el nivel Co-Prime o no,
- Primero, tenemos que almacenar todos los números primos usando la Tamiz de Eratóstenes .
- Luego, tenemos que hacer un recorrido de orden de nivel del árbol binario y guardar todos los elementos de ese nivel en un vector.
- Este vector se utiliza para almacenar los niveles del árbol mientras se realiza el recorrido del orden de niveles.
- Luego, para cada nivel, verifique si los elementos tienen un GCD igual a 1 o no. En caso afirmativo, este nivel no es Co-Prime, de lo contrario, imprima todos los elementos de ese nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for printing Co-prime
// levels of binary Tree
#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 entries it 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 whether Level
// is Co-prime or not
bool isLevelCo_Prime(vector<int>& L)
{
int max = 0;
for (auto x : L) {
if (max < x)
max = x;
}
for (int i = 0;
i * prime[i] <= max / 2;
i++) {
int ct = 0;
for (auto x : L) {
if (x % prime[i] == 0)
ct++;
}
// If not co-prime
if (ct > 1) {
return false;
}
}
return true;
}
// Function to print a Co-Prime level
void printCo_PrimeLevels(vector<int>& Lev)
{
for (auto x : Lev) {
cout << x << " ";
}
cout << endl;
}
// Utility function to get Co-Prime
// Level of a given Binary tree
void findCo_PrimeLevels(
struct Node* node,
struct Node* queue[],
int index, int size)
{
vector<int> Lev;
// Run while loop
while (index < size) {
int curr_size = size;
// Run inner while loop
while (index < curr_size) {
struct Node* temp = queue[index];
Lev.push_back(temp->key);
// Push left child in a queue
if (temp->left != NULL)
queue[size++] = temp->left;
// Push right child in a queue
if (temp->right != NULL)
queue[size++] = temp->right;
// Increment index
index++;
}
// If condition to check, level is
// prime or not
if (isLevelCo_Prime(Lev)) {
// Function call to print
// prime level
printCo_PrimeLevels(Lev);
}
Lev.clear();
}
}
// Function to find total no of nodes
// In a given binary tree
int findSize(struct Node* node)
{
// Base condition
if (node == NULL)
return 0;
return 1
+ findSize(node->left)
+ findSize(node->right);
}
// Function to find Co-Prime levels
// In a given binary tree
void printCo_PrimeLevels(struct Node* node)
{
int t_size = findSize(node);
// Create queue
struct Node* queue[t_size];
// Push root node in a queue
queue[0] = node;
// Function call
findCo_PrimeLevels(node, queue, 0, 1);
}
// Driver Code
int main()
{
/* 10
/ \
48 12
/ \
18 35
/ \ / \
21 29 43 16
/
7
*/
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(48);
root->right = newNode(12);
root->right->left = newNode(18);
root->right->right = newNode(35);
root->right->left->left = newNode(21);
root->right->left->right = newNode(29);
root->right->right->left = newNode(43);
root->right->right->right = newNode(16);
root->right->right->right->left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Co-Prime Levels
printCo_PrimeLevels(root);
return 0;
}
Java
// Java program for printing Co-prime
// levels of binary Tree
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 entries it 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 whether Level
// is Co-prime or not
static boolean isLevelCo_Prime(Vector<Integer> L)
{
int max = 0;
for (int x : L) {
if (max < x)
max = x;
}
for (int i = 0;
i * prime.get(i) <= max / 2;
i++) {
int ct = 0;
for (int x : L) {
if (x % prime.get(i) == 0)
ct++;
}
// If not co-prime
if (ct > 1) {
return false;
}
}
return true;
}
// Function to print a Co-Prime level
static void printCo_PrimeLevels(Vector<Integer> Lev)
{
for (int x : Lev) {
System.out.print(x+ " ");
}
System.out.println();
}
// Utility function to get Co-Prime
// Level of a given Binary tree
static void findCo_PrimeLevels(
Node node,
Node queue[],
int index, int size)
{
Vector<Integer> Lev = new Vector<Integer>();
// Run while loop
while (index < size) {
int curr_size = size;
// Run inner while loop
while (index < curr_size) {
Node temp = queue[index];
Lev.add(temp.key);
// Push left child in a queue
if (temp.left != null)
queue[size++] = temp.left;
// Push right child in a queue
if (temp.right != null)
queue[size++] = temp.right;
// Increment index
index++;
}
// If condition to check, level is
// prime or not
if (isLevelCo_Prime(Lev)) {
// Function call to print
// prime level
printCo_PrimeLevels(Lev);
}
Lev.clear();
}
}
// Function to find total no of nodes
// In a given binary tree
static int findSize(Node node)
{
// Base condition
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to find Co-Prime levels
// In a given binary tree
static void printCo_PrimeLevels(Node node)
{
int t_size = findSize(node);
// Create queue
Node []queue = new Node[t_size];
// Push root node in a queue
queue[0] = node;
// Function call
findCo_PrimeLevels(node, queue, 0, 1);
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
48 12
/ \
18 35
/ \ / \
21 29 43 16
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(48);
root.right = newNode(12);
root.right.left = newNode(18);
root.right.right = newNode(35);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(16);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Co-Prime Levels
printCo_PrimeLevels(root);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for printing # Co-prime levels of binary Tree # A Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create # a new node def newNode(key): temp = Node(key) return temp N = 1000000 # Vector to store all the # prime numbers prime = [] # Function to store all the # prime numbers in an array def SieveOfEratosthenes(): # Create a boolean array "prime[0..N]" # and initialize all the entries in it # as true. A value in prime[i] # will finally be false if # i is Not a prime, else true. check = [True for i 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 # Function to check whether # Level is Co-prime or not def isLevelCo_Prime(L): max = 0; for x in L: if (max < x): max = x; i = 0 while(i * prime[i] <= max // 2): ct = 0; for x in L: if (x % prime[i] == 0): ct += 1 # If not co-prime if (ct > 1): return False; i += 1 return True; # Function to print a # Co-Prime Level def printCo_PrimeLevels(Lev): for x in Lev: print(x, end = ' ') print() # Utility function to get Co-Prime # Level of a given Binary tree def findCo_PrimeLevels(node, queue, index, size): Lev = [] # Run while loop while (index < size): curr_size = size; # Run inner while loop while (index < curr_size): temp = queue[index]; Lev.append(temp.key) # Push left child in a # queue if (temp.left != None): queue[size] = temp.left; size += 1 # Push right child in a queue if (temp.right != None): queue[size] = temp.right; size += 1 # Increment index index += 1 # If condition to check, level # is prime or not if (isLevelCo_Prime(Lev)): # Function call to print # prime level printCo_PrimeLevels(Lev); Lev.clear(); # Function to find total no of nodes # In a given binary tree def findSize(node): # Base condition if (node == None): return 0; return (1 + findSize(node.left) + findSize(node.right)); # Function to find Co-Prime levels # In a given binary tree def printCo_PrimeLevel(node): t_size = findSize(node); # Create queue queue = [0 for i in range(t_size)] # Push root node in a queue queue[0] = node; # Function call findCo_PrimeLevels(node, queue, 0, 1); # Driver code if __name__ == "__main__": ''' 10 / \ 48 12 / \ 18 35 / \ / \ 21 29 43 16 / 7 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(48); root.right = newNode(12); root.right.left = newNode(18); root.right.right = newNode(35); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(16); root.right.right.right.left = newNode(7); # To save all prime numbers SieveOfEratosthenes(); # Print Co-Prime Levels printCo_PrimeLevel(root); # This code is contributed by Rutvik_56
C#
// C# program for printing Co-prime
// levels of binary Tree
using System;
using System.Collections.Generic;
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 entries it 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++)
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 whether Level
// is Co-prime or not
static bool isLevelCo_Prime(List<int> L)
{
int max = 0;
foreach (int x in L) {
if (max < x)
max = x;
}
for (int i = 0;
i * prime[i] <= max / 2;
i++) {
int ct = 0;
foreach (int x in L) {
if (x % prime[i] == 0)
ct++;
}
// If not co-prime
if (ct > 1) {
return false;
}
}
return true;
}
// Function to print a Co-Prime level
static void printCo_PrimeLevels(List<int> Lev)
{
foreach (int x in Lev) {
Console.Write(x+ " ");
}
Console.WriteLine();
}
// Utility function to get Co-Prime
// Level of a given Binary tree
static void findCo_PrimeLevels(
Node node,
Node []queue,
int index, int size)
{
List<int> Lev = new List<int>();
// Run while loop
while (index < size) {
int curr_size = size;
// Run inner while loop
while (index < curr_size) {
Node temp = queue[index];
Lev.Add(temp.key);
// Push left child in a queue
if (temp.left != null)
queue[size++] = temp.left;
// Push right child in a queue
if (temp.right != null)
queue[size++] = temp.right;
// Increment index
index++;
}
// If condition to check, level is
// prime or not
if (isLevelCo_Prime(Lev)) {
// Function call to print
// prime level
printCo_PrimeLevels(Lev);
}
Lev.Clear();
}
}
// Function to find total no of nodes
// In a given binary tree
static int findSize(Node node)
{
// Base condition
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to find Co-Prime levels
// In a given binary tree
static void printCo_PrimeLevels(Node node)
{
int t_size = findSize(node);
// Create queue
Node []queue = new Node[t_size];
// Push root node in a queue
queue[0] = node;
// Function call
findCo_PrimeLevels(node, queue, 0, 1);
}
// Driver Code
public static void Main(String[] args)
{
/* 10
/ \
48 12
/ \
18 35
/ \ / \
21 29 43 16
/
7
*/
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(48);
root.right = newNode(12);
root.right.left = newNode(18);
root.right.right = newNode(35);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(16);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Co-Prime Levels
printCo_PrimeLevels(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for printing Co-prime
// levels of binary Tree
let N = 1000000;
// To store all prime numbers
let prime = [];
function SieveOfEratosthenes()
{
// Create a boolean array "prime[0..N]"
// and initialize all entries it 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 whether Level
// is Co-prime or not
function isLevelCo_Prime(L)
{
let max = 0;
for(let x = 0; x < L.length; x++)
{
if (max < L[x])
max = L[x];
}
for(let i = 0;
i * prime[i] <= parseInt(max / 2, 10);
i++)
{
let ct = 0;
for(let x = 0; x < L.length; x++)
{
if (L[x] % prime[i] == 0)
ct++;
}
// If not co-prime
if (ct > 1)
{
return false;
}
}
return true;
}
// Function to print a Co-Prime level
function printCoPrimeLevels(Lev)
{
for(let x = 0; x < Lev.length; x++)
{
document.write(Lev[x] + " ");
}
document.write("</br>");
}
// Utility function to get Co-Prime
// Level of a given Binary tree
function findCo_PrimeLevels(node, queue, index, size)
{
let Lev = [];
// Run while loop
while (index < size)
{
let curr_size = size;
// Run inner while loop
while (index < curr_size)
{
let temp = queue[index];
Lev.push(temp.key);
// Push left child in a queue
if (temp.left != null)
queue[size++] = temp.left;
// Push right child in a queue
if (temp.right != null)
queue[size++] = temp.right;
// Increment index
index++;
}
// If condition to check, level is
// prime or not
if (isLevelCo_Prime(Lev))
{
// Function call to print
// prime level
printCoPrimeLevels(Lev);
}
Lev = [];
}
}
// Function to find total no of nodes
// In a given binary tree
function findSize(node)
{
// Base condition
if (node == null)
return 0;
return 1 + findSize(node.left) +
findSize(node.right);
}
// Function to find Co-Prime levels
// In a given binary tree
function printCo_PrimeLevels(node)
{
let t_size = findSize(node);
// Create queue
let queue = new Array(t_size);
for(let i = 0; i < t_size; i++)
{
queue[i] = new Node();
}
// Push root node in a queue
queue[0] = node;
// Function call
findCo_PrimeLevels(node, queue, 0, 1);
}
// Driver code
/* 10
/ \
48 12
/ \
18 35
/ \ / \
21 29 43 16
/
7
*/
// Create Binary Tree as shown
let root = newNode(10);
root.left = newNode(48);
root.right = newNode(12);
root.right.left = newNode(18);
root.right.right = newNode(35);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(16);
root.right.right.right.left = newNode(7);
// To save all prime numbers
SieveOfEratosthenes();
// Print Co-Prime Levels
printCo_PrimeLevels(root);
// This code is contributed by mukesh07
</script>
Producción:
10 18 35 21 29 43 16 7