Given a Prufer sequence of a Tree, the task is to print the nodes with prime-degree in this tree.
Examples:
Input: arr[] = {4, 1, 3, 4}
Output: 1 3 4
Explanation:
The tree is:
2----4----3----1----5
|
6
Hence, the degree of 1, 3 and 4
are 2, 2 and 3 respectively
which are prime.
Input: a[] = {1, 2, 2}
Output: 1 2
Approach:
- Since the length of prufer sequence is N – 2 if N is the number of nodes. Therefore, create an array degree[] of size 2 more than the length of the Prufer sequence.
- Initially, fill the degree array with 1.
- Iterate in the Prufer sequence and increase the frequency in the degree table for every element. This method works because the frequency of a node in the Prufer sequence is one less than the degree in the tree.
- Further, to check if the node degree is prime or not, we will use Sieve Of eratosthenes. Create a sieve which will help us to identify if the degree is prime or not in O(1) time.
- If a node has a prime degree, then print the node number.
Below is the implementation of the above approach:
C++
// C++ implementation to print the // nodes with prime degree from the// given prufer sequence#include <bits/stdc++.h>using namespace std;// Function to create Sieve// to check primesvoid SieveOfEratosthenes( bool prime[], int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to print the nodes with// prime degree in the tree// whose Prufer sequence is givenvoid PrimeDegreeNodes(int prufer[], int n){ int nodes = n + 2; bool prime[nodes + 1]; memset(prime, true, sizeof(prime)); SieveOfEratosthenes(prime, nodes + 1); // Hash-table to mark the // degree of every node int degree[n + 2 + 1]; // Initially let all the degrees be 1 for (int i = 1; i <= nodes; i++) degree[i] = 1; // Increase the count of the degree for (int i = 0; i < n; i++) degree[prufer[i]]++; // Print the nodes with prime degree for (int i = 1; i <= nodes; i++) { if (prime[degree[i]]) { cout << i << " "; } }}// Driver Codeint main(){ int a[] = { 4, 1, 3, 4 }; int n = sizeof(a) / sizeof(a[0]); PrimeDegreeNodes(a, n); return 0;} |
Java
// Java implementation to print the // nodes with prime degree from the// given prufer sequence import java.util.*;class GFG{ // Function to create Sieve// to check primesstatic void SieveOfEratosthenes( boolean prime[], int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }} // Function to print the nodes with// prime degree in the tree// whose Prufer sequence is givenstatic void PrimeDegreeNodes(int prufer[], int n){ int nodes = n + 2; boolean []prime = new boolean[nodes + 1]; Arrays.fill(prime, true); SieveOfEratosthenes(prime, nodes + 1); // Hash-table to mark the // degree of every node int []degree = new int[n + 2 + 1]; // Initially let all the degrees be 1 for (int i = 1; i <= nodes; i++) degree[i] = 1; // Increase the count of the degree for (int i = 0; i < n; i++) degree[prufer[i]]++; // Print the nodes with prime degree for (int i = 1; i <= nodes; i++) { if (prime[degree[i]]) { System.out.print(i+ " "); } }} // Driver Codepublic static void main(String[] args){ int a[] = { 4, 1, 3, 4 }; int n = a.length; PrimeDegreeNodes(a, n); }}// This code contributed by Princi Singh |
Python3
# Python3 implementation to print the # nodes with prime degree from the# given prufer sequence# Function to create Sieve# to check primesdef SieveOfEratosthenes(prime, p_size): # False here indicates # that it is not prime prime[0] = False prime[1] = False p = 2 while (p * p <= p_size): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p, # set them to non-prime for i in range(p * 2, p_size + 1, p): prime[i] = False p += 1 # Function to print the nodes with# prime degree in the tree# whose Prufer sequence is givendef PrimeDegreeNodes(prufer, n): nodes = n + 2 prime = [True] * (nodes + 1) SieveOfEratosthenes(prime, nodes + 1) # Hash-table to mark the # degree of every node degree = [0] * (n + 2 + 1); # Initially let all the degrees be 1 for i in range(1, nodes + 1): degree[i] = 1; # Increase the count of the degree for i in range(0, n): degree[prufer[i]] += 1 # Print the nodes with prime degree for i in range(1, nodes + 1): if prime[degree[i]]: print(i, end = ' ')# Driver Codeif __name__=='__main__': a = [ 4, 1, 3, 4 ] n = len(a) PrimeDegreeNodes(a, n)# This code is contributed by rutvik_56 |
C#
// C# implementation to print the // nodes with prime degree from the// given prufer sequenceusing System;class GFG{// Function to create Sieve// to check primesstatic void SieveOfEratosthenes(bool []prime, int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for(int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for(int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to print the nodes with// prime degree in the tree// whose Prufer sequence is givenstatic void PrimeDegreeNodes(int []prufer, int n){ int nodes = n + 2; bool []prime = new bool[nodes + 1]; for(int i = 0; i < prime.Length; i++) prime[i] = true; SieveOfEratosthenes(prime, nodes + 1); // Hash-table to mark the // degree of every node int []degree = new int[n + 2 + 1]; // Initially let all the degrees be 1 for(int i = 1; i <= nodes; i++) degree[i] = 1; // Increase the count of the degree for(int i = 0; i < n; i++) degree[prufer[i]]++; // Print the nodes with prime degree for(int i = 1; i <= nodes; i++) { if (prime[degree[i]]) { Console.Write(i + " "); } }}// Driver Codepublic static void Main(String[] args){ int []a = { 4, 1, 3, 4 }; int n = a.Length; PrimeDegreeNodes(a, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation to print the// nodes with prime degree from the// given prufer sequence// Function to create Sieve// to check primesfunction SieveOfEratosthenes(prime, p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (let p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (let i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to print the nodes with// prime degree in the tree// whose Prufer sequence is givenfunction PrimeDegreeNodes(prufer, n){ let nodes = n + 2; let prime = new Array(nodes + 1); prime.fill(true); SieveOfEratosthenes(prime, nodes + 1); // Hash-table to mark the // degree of every node let degree = new Array(n + 2 + 1); // Initially let all the degrees be 1 for (let i = 1; i <= nodes; i++) degree[i] = 1; // Increase the count of the degree for (let i = 0; i < n; i++) degree[prufer[i]]++; // Print the nodes with prime degree for (let i = 1; i <= nodes; i++) { if (prime[degree[i]]) { document.write(i + " "); } }}// Driver Codelet a = [ 4, 1, 3, 4 ];let n = a.lengthPrimeDegreeNodes(a, n);// This code is contributed by gfgking</script> |
Output:
1 3 4
Time Complexity: O(n*log(log(n))) + O(n) which is asymptotically equal to O(n*log(log(n))).
Space Complexity: O(n) as arrays has been created to store values.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
