Find k numbers which are powers of 2 and have sum N | Set 1 | CPP program to find k numbers that are power of 2 and have sum equal to N ; function to print numbers ; Count the number of set bits ; Not - possible condition ; Stores the number ; Get the set bits ; Iterate till we get K elements ; Get the topmost element ; Push the elements / 2 into priority queue ; Print all elements ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printNum ( int n , int k ) { int x = __builtin_popcount ( n ) ; if ( k < x k > n ) { cout << " - 1" ; return ; } priority_queue < int > pq ; int two = 1 ; while ( n ) { if ( n & 1 ) { pq . push ( two ) ; } two = two * 2 ; n = n >> 1 ; } while ( pq . size ( ) < k ) { int el = pq . top ( ) ; pq . pop ( ) ; pq . push ( el / 2 ) ; pq . push ( el / 2 ) ; } int ind = 0 ; while ( ind < k ) { cout << pq . top ( ) << " ▁ " ; pq . pop ( ) ; ind ++ ; } } int main ( ) { int n = 9 , k = 4 ; printNum ( n , k ) ; return 0 ; }