Find k numbers which are powers of 2 and have sum N | Set 1 | Java 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
import java . io . * ; import java . util . * ; class GFG { static void printNum ( int n , int k ) { String str = Integer . toBinaryString ( n ) ; int x = 0 ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) if ( str . charAt ( i ) == '1' ) x ++ ; if ( k < x k > n ) { System . out . println ( " - 1" ) ; return ; } PriorityQueue < Integer > pq = new PriorityQueue < > ( Comparator . reverseOrder ( ) ) ; int two = 1 ; while ( n > 0 ) { if ( ( n & 1 ) == 1 ) pq . add ( two ) ; two *= 2 ; n = n >> 1 ; } while ( pq . size ( ) < k ) { int el = pq . poll ( ) ; pq . add ( el / 2 ) ; pq . add ( el / 2 ) ; } int ind = 0 ; while ( ind < k ) { System . out . print ( pq . poll ( ) + " ▁ " ) ; ind ++ ; } } public static void main ( String [ ] args ) { int n = 9 , k = 4 ; printNum ( n , k ) ; } }