Count the nodes in the given tree whose weight is a powerful number | Javascript 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 ; Weights of the node ; Edges of the tree
var ans = 0 ; var graph = Array . from ( Array ( 100 ) , ( ) => Array ( ) ) ; var weight = Array . from ( Array ( 100 ) , ( ) => Array ( ) ) ; function isPowerful ( n ) { while ( n % 2 == 0 ) { var power = 0 ; while ( n % 2 == 0 ) { n /= 2 ; power ++ ; } if ( power == 1 ) return false ; } for ( var factor = 3 ; factor <= Math . sqrt ( n ) ; factor += 2 ) { var power = 0 ; while ( n % factor == 0 ) { n = n / factor ; power ++ ; } if ( power == 1 ) return false ; } return ( n == 1 ) ; } function dfs ( node , parent ) { if ( isPowerful ( weight [ node ] ) ) ans += 1 ; graph [ node ] . forEach ( to => { if ( to != parent ) dfs ( to , node ) ; } ) ; } weight [ 1 ] = 5 ; weight [ 2 ] = 10 ; weight [ 3 ] = 11 ; weight [ 4 ] = 8 ; weight [ 5 ] = 6 ; graph [ 1 ] . push ( 2 ) ; graph [ 2 ] . push ( 3 ) ; graph [ 2 ] . push ( 4 ) ; graph [ 1 ] . push ( 5 ) ; dfs ( 1 , 1 ) ; document . write ( ans ) ;