Cho N, K. In K số là lũy thừa 2 tổng bằng N. Không thể thì -1. N=9, K=4, kết quả 4 2 2 1, tổng 9, 4 phần tử, đều lũy thừa 2.
Giải quyết:
- Nếu k < số bit 1 của N hoặc k > N thì -1
- Thêm lũy thừa 2 tại bit 1 vào priority queue
- Mở rộng queue đến K phần tử: lấy phần tử lớn nhất, chia 2 đẩy lại hai lần
- Đạt K phần tử thì in ra
Ví dụ mã nguồn
#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); } Kết quả
Numbers are: 8 8 8 4 2