मान लीजिए हमारे पास दो संख्याएं N और K हैं। कार्य K संख्याएं प्रिंट करना है जो 2 की घात (powers of 2) हैं और जिनका योग N है। यदि संभव नहीं है, तो -1 लौटाएं। उदाहरण: N=9, K=4 के लिए आउटपुट 4, 2, 2, 1 होगा (योग=9, तत्व=4, प्रत्येक 2 की घात)।
हल करने के चरण
- यदि K, N में सेट बिट्स की संख्या से कम है या N से अधिक है, तो -1 लौटाएं।
- N के सेट बिट्स पर 2 की घातों को प्रायोरिटी क्यू (मैक्स-हीप) में डालें।
- जब तक क्यू का आकार K से कम है:
- सबसे बड़ा तत्व निकालें।
- उस तत्व को 2 से विभाजित करके दो बार वापस क्यू में डालें।
- 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<int> pq;
int two = 1;
while (n) {
if (n & 1)
pq.push(two);
two *= 2;
n >>= 1;
}
while (pq.size() < k) {
int element = pq.top();
pq.pop();
pq.push(element / 2);
pq.push(element / 2);
}
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
}
int main() {
int n = 30, k = 5;
cout << "Numbers are: ";
displayKnumbers(n, k);
return 0;
}
आउटपुट
Numbers are: 8 8 8 4 2