CAB Editorial - Non Official

editorial
1

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]
1 Like