2の累乗であり、C++で合計Nを持つk個の数値を見つけます

NとKの2つの数値があるとします。タスクは、2の累乗で合計がNであるKの数値を出力することです。それが不可能な場合は、-1を返します。 。 N=9およびK=4とすると、出力は4 2 2 1になり、その合計は9で、要素の数は4であり、それぞれが2の累乗です。

この問題を解決するには、次の手順に従う必要があります-

• kがNのセットビット数よりも小さいか、Nよりも大きい場合は、-1を返します

  。

• 設定されたビットで2の累乗を優先キューに追加します

• K個の要素を取得するまで優先キューを開始してから、その要素を優先キューから削除します

• 削除した要素/2を優先キューに再度2回挿入します

• k個の要素が達成されたら、それらを印刷します。

例

#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