在C ++中找到k的2的幂并具有N的数字

假设我们有两个数字N和K。任务是打印K个数字,它们是2的幂,并且它们的和是N。如果不可能,则返回-1。假设N = 9且K = 4,则输出为4 2 2 1,其总和为9,元素个数为4,每个元素的乘方为2。

我们必须按照以下步骤来解决这个问题-

  • 如果k小于N中的设置位数或大于N,则返回-1

  • 将设置位的2的幂加到Priority队列中

  • 启动优先级队列,直到获得K个元素,然后从优先级队列中删除该元素

  • 再次将删除的element / 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