โปรแกรม 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
• เพิ่มกำลังของสองที่บิตตั้งค่าลงใน Priority queue
• เริ่มต้น priority queue จนกว่าเราจะได้ K องค์ประกอบ จากนั้นลบองค์ประกอบออกจาก priority queue
• แทรกองค์ประกอบที่ลบออก / 2 สองครั้งลงใน priority queue อีกครั้ง
• หากได้ k องค์ประกอบแล้ว ให้พิมพ์พวกเขา

ตัวอย่างโค้ด C++

#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 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