Given two numbers N and K. The task is to print K numbers which are powers of 2 and their sum is N. Print -1 if not possible.
Examples:
Input: N = 9, K = 4 Output: 4 2 2 1 4 + 2 + 2 + 1 = 9 Input: N = 4, K = 5 Output: -1
Approach: The below algorithm can be followed to solve the above problem:
- 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.
- Once K elements are achieved, print them.
Below is the implementation of the above approach:
C++
// CPP program to find k numbers that // are power of 2 and have sum equal // to N#include <bits/stdc++.h>using namespace std;// function to print numbersvoid 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 Codeint main(){ int n = 9, k = 4; printNum(n, k); return 0;} |
Java
// Java program to find k numbers that // are power of 2 and have sum equal // to N import java.io.*;import java.util.*;class GFG { // function to print numbers static void printNum(int n, int k) { // Count the number of set bits String str = Integer.toBinaryString(n); int x = 0; for (int i = 0; i < str.length(); i++) if (str.charAt(i) == '1') x++; // Not-possible condition if (k < x || k > n) { System.out.println("-1"); return; } // Stores the number PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // Get the set bits int two = 1; while (n > 0) { if ((n & 1) == 1) pq.add(two); two *= 2; n = n >> 1; } // Iterate till we get K elements while (pq.size() < k) { // Get the topmost element int el = pq.poll(); // Push the elements/2 into // priority queue pq.add(el / 2); pq.add(el / 2); } // Print all elements int ind = 0; while (ind < k) { System.out.print(pq.poll() + " "); ind++; } } // Driver Code public static void main(String[] args) { int n = 9, k = 4; printNum(n, k); }}// This code is contributed by// sanjeev2552 |
Python
# Python program to find k numbers that # are power of 2 and have sum equal # to N # function to print numbers def printNum(n, k): # Count the number of set bits x = 0 m = n while (m): x += m & 1 m >>= 1 # Not-possible condition if k < x or k > n: print("-1") return # Stores the number pq = [] # Get the set bits two = 1 while (n): if (n & 1): pq.append(two) two = two * 2 n = n >> 1 # Iterate till we get K elements while (len(pq) < k): # Get the topmost element el = pq[-1] pq.pop() # append the elements/2 into # priority queue pq.append(el // 2) pq.append(el // 2) # Print all elements ind = 0 pq.sort() while (ind < k): print(pq[-1], end = " ") pq.pop() ind += 1# Driver Code n = 9k = 4printNum(n, k) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find k numbers that// are power of 2 and have sum equal// to Nusing System;using System.Collections.Generic;public class GFG { // function to print numbers static void printNum(int n, int k) { // Count the number of set bits int x = 0; int m = n; while (m > 0) { x += m & 1; m >>= 1; } // Not-possible condition if (k < x || k > n) { Console.WriteLine("-1"); return; } // Stores the number List<int> pq = new List<int>(); // Get the set bits int two = 1; while (n > 0) { if ((n & 1) != 0) pq.Add(two); two = two * 2; n = n >> 1; } // Iterate till we get K elements while (pq.Count < k) { // Get the topmost element int el = pq[pq.Count - 1]; pq.RemoveAt(pq.Count - 1); // append the elements/2 into // priority queue pq.Add(el / 2); pq.Add(el / 2); } // Print all elements int ind = 0; pq.Sort(); while (ind < k) { Console.Write(pq[pq.Count - 1] + " "); pq.RemoveAt(pq.Count - 1); ind += 1; } } // Driver code public static void Main(string[] args) { int n = 9; int k = 4; printNum(n, k); }}// This code is contributed by phasing17 |
Javascript
<script>// JavaScript program to find k numbers that // are power of 2 and have sum equal // to N // function to print numbers function printNum(n, k){ // Count the number of set bits let x = 0 let m = n while (m){ x += m & 1 m >>= 1 } // Not-possible condition if(k < x || k > n){ document.write("-1","</br>") return } // Stores the number let pq = [] // Get the set bits let two = 1 while (n){ if (n & 1) pq.push(two) two = two * 2 n = n >> 1 } // Iterate till we get K elements while (pq.length < k){ // Get the topmost element let el = pq[pq.length -1] pq.pop() // push the elements/2 into // priority queue pq.push(Math.floor(el / 2)) pq.push(Math.floor(el / 2)) } // Print all elements let ind = 0 pq.sort() while (ind < k){ document.write(pq[pq.length -1]," ") pq.pop() ind += 1 }}// Driver Code let n = 9let k = 4printNum(n, k) // This code is contributed by shinjanpatra</script> |
Output:
4 2 2 1
Time Complexity: O(N*logN), as we are using a loop to traverse N times and in each traversal we are using priority queue operation which will cost logN time.
Auxiliary Space: O(N), as we are using extra space for the priority queue.
Represent n as the sum of exactly k powers of two | Set 2
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/find-k-numbers-which-are-powers-of-2-and-have-sum-n-set-1/ […]