ধরুন আমাদের দুটি সংখ্যা 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
