Idea :
- If the K is less than the number of set bits in N or more than the number N, then it is not possible.
- Insert the powers of two at set bits into Priority Queue.
- Iterate in the Priority Queue till we get K elements, pop() the topmost element and
- push element/2 twice into the Priority Queue again.
Easy solution :
#include <bits/stdc++.h>
using
namespace
std;
// function to print numbers
void
printNum(
int
n,
int
k)
{
// Count the number of set bits
int
x = __builtin_popcount(n);
// Not-possible condition
if
(k < x || k > n) {
cout <<
"-1"
;
return
;
}
// Stores the number
priority_queue<
int
> pq;
// Get the set bits
int
two = 1;
while
(n) {
if
(n & 1) {
pq.push(two);
}
two = two * 2;
n = n >> 1;
}
// Iterate till we get K elements
while
(pq.size() < k) {
// Get the topmost element
int
el = pq.top();
pq.pop();
// Push the elements/2 into
// priority queue
pq.push(el / 2);
pq.push(el / 2);
}
// Print all elements
int
ind = 0;
while
(ind < k) {
cout << pq.top() <<
" "
;
pq.pop();
ind++;
}
}
// Driver Code
int
main()
{
int
n = 9, k = 4;
printNum(n, k);
return
0;
}
any doubt ask. [poll type=multiple results=always min=1 max=2 public=true chartType=bar]
How is editorial?
- Like
- Not like
[/poll]