Count the nodes in the given tree whose weight is a powerful number | Java implementation to Count the nodes in the given tree whose weight is a powerful number ; Function to check if the number is powerful ; First divide the number repeatedly by 2 ; Check if only 2 ^ 1 divides n , then return false ; Check if n is not a power of 2 then this loop will execute ; Find highest power of " factor " that divides n ; Check if only factor ^ 1 divides n , then 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. ; Function to perform dfs ; Check if weight of the current node is a powerful number ; Driver code ; Weights of the node ; Edges of the tree
import java . util . * ; class GFG { static int ans = 0 ; static Vector < Integer > [ ] graph = new Vector [ 100 ] ; static int [ ] weight = new int [ 100 ] ; static boolean isPowerful ( int n ) { while ( n % 2 == 0 ) { int power = 0 ; while ( n % 2 == 0 ) { n /= 2 ; power ++ ; } if ( power == 1 ) return false ; } for ( int factor = 3 ; factor <= Math . sqrt ( n ) ; factor += 2 ) { int power = 0 ; while ( n % factor == 0 ) { n = n / factor ; power ++ ; } if ( power == 1 ) return false ; } return ( n == 1 ) ; } static void dfs ( int node , int parent ) { if ( isPowerful ( weight [ node ] ) ) ans += 1 ; for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node ) ; } } public static void main ( String [ ] args ) { for ( int i = 0 ; i < graph . length ; i ++ ) graph [ i ] = new Vector < Integer > ( ) ; weight [ 1 ] = 5 ; weight [ 2 ] = 10 ; weight [ 3 ] = 11 ; weight [ 4 ] = 8 ; weight [ 5 ] = 6 ; graph [ 1 ] . add ( 2 ) ; graph [ 2 ] . add ( 3 ) ; graph [ 2 ] . add ( 4 ) ; graph [ 1 ] . add ( 5 ) ; dfs ( 1 , 1 ) ; System . out . print ( ans ) ; } }