นับโหนดที่น้ำหนักเป็นกำลังของ 2 (Power of Two) ใน C++

โจทย์: ให้ Binary Tree ที่โหนดมีน้ำหนักเป็นจำนวนเต็ม ต้องการนับโหนดที่น้ำหนักเป็นกำลังของ 2 (1, 2, 4, 8, 16, 32, 64...)

การตรวจสอบกำลังของ 2 ด้วย Bitwise

จำนวน n เป็นกำลังของ 2 ก็ต่อเมื่อ n & (n - 1) == 0 และ n > 0

if (set && !(set & (set - 1)))  // เป็นกำลังของ 2

DFS นับโหนด

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);
    }
}

ตัวอย่างเต็ม

#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;      // 2³
    Node_Weight[1] = 100;    // ไม่ใช่
    Node_Weight[4] = 211;    // ไม่ใช่
    Node_Weight[3] = 16;     // 2⁴
    Node_Weight[8] = 7171;   // ไม่ใช่
    Node_Weight[9] = 32;     // 2⁵
    
    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: " << powers;
    return 0;
}

ผลลัพธ์

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

โหนดที่เป็นกำลังของ 2: 8, 16, 32 = 3 โหนด

หมายเหตุ: ตารางตัวอย่างที่ 2 ในเนื้อหาเดิมมีข้อมูลไม่สอดคล้อง (81 เป็น 9² ไม่ใช่ 2ⁿ) โค้ดตัวอย่างจริงใช้ค่าต่างออกไป