C++で重みが2の累乗となる木のノードを数える方法

各ノードに「重み」が割り当てられた二分木が与えられます。この記事の目的は、重みが2の累乗（べき乗）になっているノードの個数を求めることです。たとえば重みが32であれば 32 = 2⁵ なので、このノードはカウントの対象となります。

入力例1

入力した値から生成される木は次のようになります。

出力

与えられた木のうち、重みが2の累乗であるノードの数: 3

説明

木の各ノードと、それぞれに対応する重みが与えられています。そこで、すべての重みについて「2の累乗として表せるかどうか」を順に判定していきます。

入力例2

別の入力値から生成される木は次のようになります。

出力

与えられた木のうち、重みが2の累乗であるノードの数: 2

説明

同様に、各ノードの重みが2の累乗かどうかを確認します。

プログラムで使用するアプローチ

このアプローチでは、木に対してDFS（深さ優先探索）を適用して全ノードを走査し、各ノードの重みが2の累乗かどうかを判定します。そのために、Node_Weight(100) と edge_graph[100] という2つのvectorを用意します。

• Node_Weight[] を各ノードの重みで初期化します。
• vector の edge_graph を使って木（グラフ）を構築します。
• グローバル変数 powers を宣言し、0で初期化します。
• 関数 power_two(int node, int root) は、現在のノードとその親ノードを受け取り、重みが2の累乗であるノードの数をカウントします。
• set = Node_Weight[node] として、現在のノードの重みを取得します。
• set && (!(set & (set - 1))) が真であれば、その値は2の累乗です。これはビットごとのANDと否定を組み合わせた定番の判定方法で、正の整数 x について x & (x-1) が0になるのは x が2の累乗の場合だけです。
• 条件を満たした場合、set の値が2の累乗であるため powers をインクリメントします。
• forループで edge_graph[node] 内の隣接ノードを走査します。
• ベクトル内の次のノードに対して power_two(it, node) を再帰的に呼び出します。
• すべての再帰呼び出しが完了した時点で、powers には重みが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(){
    // 各ノードの重み
    Node_Weight[2] = 8;
    Node_Weight[1] = 100;
    Node_Weight[4] = 211;
    Node_Weight[3] = 16;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 32;
    // グラフの辺を作成
    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<<"与えられた木のうち、重みが2の累乗であるノードの数: "<<powers;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

与えられた木のうち、重みが2の累乗であるノードの数: 3