২-এর ঘাত গঠিত Kটি সংখ্যা যাদের যোগফল N (C++)

দুটি সংখ্যা N এবং K দেওয়া আছে। ২-এর ঘাত গঠিত Kটি সংখ্যা খুঁজে বের করতে হবে যাদের যোগফল N। N=9, K=4 -> 4,2,2,1।

প্রায়োরিটি কিউ (ম্যাক্স হিপ) ব্যবহার করুন। N-এর সেট বিটগুলোকে পিউশ করুন। K তে পৌঁছানোর পর্যন্ত টপ এলিমেন্ট পপ করে তার হাফ দুবার পুশ করুন।

উদাহরণ

#include <iostream>
#include <queue>
using namespace std;

void displayKnumbers(int n, int k) {
    int bits = __builtin_popcount(n);
    if (k < bits || k > n) { cout << -1; return; }
    priority_queue pq;
    int two = 1;
    while (n) {
        if (n & 1) pq.push(two);
        two <<= 1; n >>= 1;
    }
    while (pq.size() < k) {
        int x = pq.top(); pq.pop();
        pq.push(x/2); pq.push(x/2);
    }
    while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
}

int main() { displayKnumbers(30, 5); return 0; }

আউটপুট

Numbers are: 8 8 8 4 2