C++で解く「積が2の累乗になる部分列」の個数を求めるアルゴリズム

この記事では、N個の整数からなる配列が与えられたとき、「要素の積が2の累乗（べき乗）になるような部分列」の個数を求める問題を解説します。

問題の例

入力： arr = [2, 5, 4]

出力： 3

説明： 部分列 [2]、[4]、[2, 4] の積はそれぞれ 2、4、8 となり、いずれも2の累乗に一致します。

解法のポイント

積が2の累乗になるためには、選ぶすべての要素が2の累乗である必要があります。なぜなら、2以外の素因数（たとえば5や3など）を含む数を掛け合わせると、その積には必ず2以外の素因数が残るためです。

つまり、この問題は次のように言い換えられます。

「配列の中から2の累乗である要素をすべて見つけ、その要素だけで作れる空でない部分列の総数を求める」

配列内に2の累乗の要素が M 個ある場合、各要素を「選ぶ／選ばない」の2択で組み合わせると 2^M 通りありますが、1つも選ばない場合（空の部分列）は除外するため、答えは 2^M − 1 となります。

2の累乗の判定にビット演算を活用

ある正の整数 n が2の累乗かどうかは、ビット演算 n & (n - 1) を使うと効率的に判定できます。n が2の累乗の場合、2進数表現では最上位の1桁だけが1となっているため、n − 1 との論理積は必ず0になります。

• 8 = 1000₂、7 = 0111₂ → 8 & 7 = 0（2の累乗）
• 6 = 0110₂、5 = 0101₂ → 6 & 5 = 4 ≠ 0（2の累乗ではない）

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;

// 数値が2の累乗かどうかを判定する関数
bool isPowerTwo(int num) {
    if (num == 0)
        return false;
    if (num == 1)
        return true;
    if (num & (num - 1))
        return false;
    return true;
}

// 積が2の累乗になる部分列の個数を返す関数
int SubsequenceWithPowerTwo(int arr[], int N) {
    int count = 0;
    for (int i = 0; i < N; i++)
        if (isPowerTwo(arr[i]))
            count++;
    return (int)(pow(2, count)) - 1;
}

int main() {
    int arr[] = {5, 4, 8, 12, 32, 9};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"積が2の累乗になる部分列の個数 : ";
    cout<<SubsequenceWithPowerTwo(arr, N)<<endl;
    return 0;
}

実行結果

積が2の累乗になる部分列の個数 : 7

処理の流れと計算量

上記の例では、配列 {5, 4, 8, 12, 32, 9} のうち2の累乗に該当するのは 4、8、32 の3つです。したがって M = 3 となり、答えは 2³ − 1 = 7 個となります。

このアルゴリズムの計算量は、配列を一度走査するだけなので O(N) です。各要素の2の累乗判定もビット演算により定数時間で行えるため、非常に効率的な解法といえます。