C++で重みが2の累乗である特定のツリー内のノードをカウントします

例

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count the nodes in the given tree whose weight is a power of two are: 3

説明

we are given with the tree node and the weights associated with each
node. Now we calculate the power of each and every weight and check whether it can
be expressed as power of 2 or not.

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count the nodes in the given tree whose weight is a power of two are: 3

説明

we are given with the tree node and the weights associated with each
node. Now we calculate the digit sum of each and every weight and check whether it's
odd or not.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、ツリーのグラフにDFSを適用してトラバースし、ノードの重みが2の累乗であるかどうかを確認します。この目的のために2つのベクトルNode_Weight（100）とedge_graph[100]を取ります。

• Node_Weight[]をノードの重みで初期化します。

• ベクトルedge_graphを使用してツリーを作成します。

• グローバル変数の合計を取り、0で初期化します。

• 関数power_two（int node、int root）は、ツリーのノードとルートノードを取得し、重みが2の累乗である指定されたツリー内のノードの数を返します。

• set =Node_Weight [node];

  を取得します

• set &&（！（set＆（set − 1）））がtrueを返す場合、それは2の累乗です（ビット単位のANDと否定）

• 設定された増分累乗の値は2の累乗です。

• forループを使用してベクトルedge_graph[node]のツリーをトラバースします。

• ベクトル内の次のノードに対してpower_two（it、node）を呼び出します。

• すべての関数の最後に、2の累乗として値を持つ重みを持つノードの数として累乗があります。

例

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int powers = 0;
void power_two(int node, int root){
   int set = Node_Weight[node];
   if(set && (!(set & (set − 1)))){
      powers++;
   }
   for(int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      power_two(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 8;
   Node_Weight[1] = 100;
   Node_Weight[4] = 211;
   Node_Weight[3] = 16;
   Node_Weight[8] = 7171;
   Node_Weight[9] = 32;
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   power_two(2, 2);
   cout<<"Count the nodes in the given tree whose weight is a power of two are: "<<powers;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count the nodes in the given tree whose weight is a power of two are: 3