C++で合計がNとなる2の累乗の数をK個見つける方法

問題の概要

2つの整数 N と K が与えられたとします。求めるのは、それぞれが 2 の累乗であり、かつ合計が N となる K 個の数値です。そのような組み合わせが存在しない場合は -1 を返します。

例として、N = 9、K = 4 の場合を考えてみましょう。このとき出力は「4 2 2 1」となります。合計は 9、要素数は 4 であり、各要素がすべて 2 の累乗になっていることが確認できます。

解法のアプローチ

この問題は、優先度付きキュー（プライオリティキュー）を活用することで効率的に解くことができます。解法の手順は以下の通りです。

• K が N のセットビット数（2進表現で 1 になっているビットの個数）より小さい場合、または N より大きい場合は -1 を返します。セットビット数は必要な要素数の最小値、N 自体は最大値（すべて 1 で構成する場合）に相当するためです。
• N のセットビットに対応する 2 の累乗を優先度付きキューに追加します。
• キューの要素数が K に達するまで、最大の要素を取り出し、その半分の値を 2 つキューに戻す操作を繰り返します。
• 要素数が K に達したら、すべての要素を出力します。

C++による実装例

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
void displayKnumbers(int n, int k) {
   int set_bit_count = __builtin_popcount(n);
   if (k < set_bit_count || k > n) {
      cout << "-1";
      return;
   }
   priority_queue<int> queue;
   int two = 1;
   while (n) {
      if (n & 1) {
         queue.push(two);
      }
      two = two * 2;
      n = n >> 1;
   }
   while (queue.size() < k) {
      int element = queue.top();
      queue.pop();
      queue.push(element / 2);
      queue.push(element / 2);
   }
   int ind = 0;
   while (ind < k) {
      cout << queue.top() << " ";
      queue.pop();
      ind++;
   }
}
int main() {
   int n = 30, k = 5;
   cout << "Numbers are: ";
   displayKnumbers(n, k);
}

実行結果

Numbers are: 8 8 8 4 2

コードの解説

まず、__builtin_popcount 関数を使って N のセットビット数を求め、解が存在するかどうかを判定しています。その後、N を右シフトしながら各ビットを調べ、セットビットに対応する 2 の累乗をキューに格納していきます。

サンプルコードでは N = 30、K = 5 を指定しています。30 は 2 進数で「11110」と表されるため、初期状態のキューには 16、8、4、2 が入ります。要素数を 5 に増やすため、最大値の 16 を取り出して 8 を 2 つ挿入します。その結果、キューは 8、8、8、4、2 となり、合計は 30 になります。

分割操作は最大で K 回行われ、各操作には優先度付きキューの性質上 O(log K) のコストがかかるため、全体の計算量は O(K log K) と評価できます。非常にシンプルでありながら効率的なアプローチです。