두 개의 숫자 N과 K가 있다고 가정합니다. 작업은 2의 거듭제곱이고 합이 N인 K 숫자를 인쇄하는 것입니다. 가능하지 않으면 -1을 반환합니다. . N =9이고 K =4라고 가정하면 출력은 4 2 2 1이 되고 합은 9이고 요소의 수는 4이고 각각은 2의 거듭제곱입니다.
이 문제를 해결하려면 다음 단계를 따라야 합니다 -
-
k가 N에 설정된 비트 수보다 작거나 N보다 크면 -1을 반환합니다.
-
우선 순위 대기열에 설정된 비트에서 2의 거듭제곱을 추가합니다.
-
K개의 요소를 얻을 때까지 우선 순위 대기열을 시작한 다음 우선 순위 대기열에서 요소를 제거합니다.
-
제거된 element/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