สมมุติว่าเรามีตัวเลข N และ K สองตัว ภารกิจคือการพิมพ์ตัวเลข K ซึ่งเป็นกำลังของ 2 และผลรวมของมันคือ N หากไม่สามารถทำได้ ให้คืนค่า -1 . สมมติว่า N =9 และ K =4 ผลลัพธ์จะเป็น 4 2 2 1 ซึ่งผลรวมคือ 9 และองค์ประกอบจำนวนหนึ่งคือ 4 และแต่ละองค์ประกอบมีกำลัง 2
เราต้องทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้ -
-
ถ้า k น้อยกว่าจำนวนชุดบิตใน N หรือมากกว่าจำนวน N ให้คืนค่า -1
-
เพิ่มกำลังสองที่บิตเซ็ตลงในคิวลำดับความสำคัญ
-
เริ่มลำดับความสำคัญจนกว่าเราจะได้องค์ประกอบ K จากนั้นลบองค์ประกอบออกจากลำดับความสำคัญ
-
ใส่องค์ประกอบที่ถูกลบ/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
