Given a Binary Tree, the task is to print all Co-prime levels of this tree.
Any level of a Binary tree is said to be a Co-prime level, if all nodes of this level are co-prime to each other.
Examples:
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.
Approach: In order to check if a level is Co-Prime level or not,
- First, we have to store all prime numbers using the Sieve of Eratosthenes.
- Then, we have to do level order traversal of the binary tree and have to save all elements of that level into a vector.
- This vector is used to store the levels of the tree while doing the level order traversal.
- Then for each level, check whether the elements have a GCD equal to 1 or not. If yes then this level is not Co-Prime, else print all elements of that level.
Below is the implementation of the above approach:
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 numbersvector<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 nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* 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 notbool 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 levelvoid printCo_PrimeLevels(vector<int>& Lev){ for (auto x : Lev) { cout << x << " "; } cout << endl;}// Utility function to get Co-Prime// Level of a given Binary treevoid 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 treeint 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 treevoid 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 Codeint 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 Treeimport java.util.*;class GFG{ static int N = 1000000; // To store all prime numbersstatic 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 nodestatic class Node { int key; Node left, right;}; // Utility function to create a new nodestatic 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 notstatic 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 levelstatic 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 treestatic 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 treestatic 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 treestatic 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 Codepublic 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 nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create# a new nodedef newNode(key): temp = Node(key) return tempN = 1000000 # Vector to store all the# prime numbersprime = [] # Function to store all the# prime numbers in an arraydef 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 notdef 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 Leveldef printCo_PrimeLevels(Lev): for x in Lev: print(x, end = ' ') print() # Utility function to get Co-Prime# Level of a given Binary treedef 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 treedef 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 treedef 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 Treeusing System;using System.Collections.Generic;class GFG{ static int N = 1000000; // To store all prime numbersstatic 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 nodeclass Node { public int key; public Node left, right;}; // Utility function to create a new nodestatic 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 notstatic 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 levelstatic 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 treestatic 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 treestatic 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 treestatic 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 Codepublic 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 Treelet N = 1000000;// To store all prime numberslet 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 nodeclass Node { constructor(key) { this.left = null; this.right = null; this.key = key; }}// Utility function to create a new nodefunction newNode(key){ let temp = new Node(key); return (temp);}// Function to check whether Level// is Co-prime or notfunction 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 levelfunction 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 treefunction 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 treefunction 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 treefunction 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 shownlet 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 numbersSieveOfEratosthenes();// Print Co-Prime LevelsprintCo_PrimeLevels(root);// This code is contributed by mukesh07 </script> |
Output:
10 18 35 21 29 43 16 7
