Giả sử chúng ta có hai số N và K. Nhiệm vụ là in ra K số, là lũy thừa của 2 và tổng của chúng là N. Nếu không được thì trả về -1 . Giả sử N =9 và K =4, thì đầu ra sẽ là 4 2 2 1, có tổng là 9 và số phần tử là 4 và mỗi phần tử có lũy thừa là 2.
Chúng tôi phải làm theo các bước sau để giải quyết vấn đề này -
-
Nếu k nhỏ hơn số bit đặt trong N hoặc nhiều hơn số N, thì trả về -1
-
Thêm lũy thừa của hai tại các bit đã đặt vào hàng đợi Ưu tiên
-
Bắt đầu hàng đợi ưu tiên cho đến khi chúng ta nhận được K phần tử, sau đó xóa phần tử khỏi hàng đợi ưu tiên
-
Chèn phần tử đã loại bỏ / 2 lần nữa vào hàng đợi ưu tiên
-
Nếu đạt được k phần tử thì hãy in chúng ra.
Ví dụ
#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);
} Đầu ra
Numbers are: 8 8 8 4 2