Given two integers N and K, the task is to find whether it is possible to represent N as the sum of exactly K powers of 2. If possible, then print K positive integers such that they are powers of 2 and their sum is exactly equal to N. Otherwise, print “Impossible”. If multiple answers exist, print any.
Examples:
Input: N = 5, K = 2
Output: 4 1
Explanation:
The only way of representing N as K numbers that are powers of 2 is {4, 1}.Input: N = 7, K = 4
Output: 4 1 1 1
Explanation:
The possible ways of representing N as K numbers that are powers of 2 are {4, 1, 1, 1} and {2, 2, 2, 1}.
Priority Queue based Approach: Refer to this article to solve the problem using Priority Queue.
Recursive Approach: Refer to this article to solve the problem using Recursion.
Alternate Approach: The idea is to use the Greedy Approach to solve this problem. Below are the steps:
- Initialize an integer, say num = 31, and a vector of integers, say res, to store the K numbers which are powers of 2.
- Check if the number of bits in N is greater than K or if N is less than K, then print “Impossible”.
- Iterate while num ? 0 and K > 0:
- Check if N – 2num is less than K – 1. If found to be true, then decrement num by one and continue.
- Otherwise, decrease K by one, and N by 2num and push num into the vector res.
- Finally, print the vector res.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find K numbers with// sum N that are powers of 2void nAsKPowersOfTwo(int N, int K){ // Count the number of set bits int x = __builtin_popcount(N); // Not-possible condition if (K < x || K > N) { cout << "Impossible"; return; } int num = 31; // To store K numbers // which are powers of 2 vector<int> res; // Traverse while num >= 0 while (num >= 0 && K) { // Calculate current bit value int val = pow(2, num); // Check if remaining N // can be represented as // K-1 numbers that are // power of 2 if (N - val < K - 1) { // Decrement num by one --num; continue; } // Decrement K by one --K; // Decrement N by val N -= val; // Push the num in the // vector res res.push_back(num); } // Print the vector res for (auto x : res) cout << pow(2, x) << " ";}// Driver Codeint main(){ // Given N & K int N = 7, K = 4; // Function Call nAsKPowersOfTwo(N, K);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find K numbers with// sum N that are powers of 2static void nAsKPowersOfTwo(int N, int K){ // Count the number of set bits int x = Integer.bitCount(N); // Not-possible condition if (K < x || K > N) { System.out.print("Impossible"); return; } int num = 31; // To store K numbers // which are powers of 2 Vector<Integer> res = new Vector<Integer>(); // Traverse while num >= 0 while (num >= 0 && K > 0) { // Calculate current bit value int val = (int) Math.pow(2, num); // Check if remaining N // can be represented as // K-1 numbers that are // power of 2 if (N - val < K - 1) { // Decrement num by one --num; continue; } // Decrement K by one --K; // Decrement N by val N -= val; // Push the num in the // vector res res.add(num); } // Print the vector res for (int i : res) System.out.print((int)Math.pow(2, i)+ " ");}// Driver Codepublic static void main(String[] args){ // Given N & K int N = 7, K = 4; // Function Call nAsKPowersOfTwo(N, K);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find K numbers with# sum N that are powers of 2def nAsKPowersOfTwo(N, K): # Count the number of set bits x = bin(N).count('1') # Not-possible condition if (K < x or K > N): cout << "Impossible" return num = 31 # To store K numbers # which are powers of 2 res = [] # Traverse while num >= 0 while (num >= 0 and K): # Calculate current bit value val = pow(2, num) # Check if remaining N # can be represented as # K-1 numbers that are # power of 2 if (N - val < K - 1): # Decrement num by one num -= 1 continue # Decrement K by one K -= 1 # Decrement N by val N -= val # Push the num in the # vector res res.append(num) # Print vector res for x in res: print(pow(2, x), end = " ")# Driver Codeif __name__ == '__main__': # Given N & K N, K = 7, 4 # Function Call nAsKPowersOfTwo(N, K)# This code is contributed mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find K numbers with// sum N that are powers of 2static void nAsKPowersOfTwo(int N, int K){ // Count the number of set bits int x = countSetBits(N); // Not-possible condition if (K < x || K > N) { Console.Write("Impossible"); return; } int num = 31; // To store K numbers // which are powers of 2 List<int> res = new List<int>(); // Traverse while num >= 0 while (num >= 0 && K > 0) { // Calculate current bit value int val = (int) Math.Pow(2, num); // Check if remaining N // can be represented as // K-1 numbers that are // power of 2 if (N - val < K - 1) { // Decrement num by one --num; continue; } // Decrement K by one --K; // Decrement N by val N -= val; // Push the num in the // vector res res.Add(num); } // Print the vector res foreach (int i in res) Console.Write((int)Math.Pow(2, i)+ " ");}static int countSetBits(long x){ int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;} // Driver Codepublic static void Main(String[] args){ // Given N & K int N = 7, K = 4; // Function Call nAsKPowersOfTwo(N, K);}}// This code is contributed by shikhasingrajput |
Javascript
<script>//Javascript program for//the above approach// Function to find K numbers with// sum N that are powers of 2function nAsKPowersOfTwo(N, K){ // Count the number of set bits var x = countSetBits(N); // Not-possible condition if (K < x || K > N) { document.write("Impossible"); return; } var num = 31; // To store K numbers // which are powers of 2 var res=[]; // Traverse while num >= 0 while (num >= 0 && K > 0) { // Calculate current bit value var val = parseInt( Math.pow(2, num)); // Check if remaining N // can be represented as // K-1 numbers that are // power of 2 if (N - val < K - 1) { // Decrement num by one --num; continue; } // Decrement K by one --K; // Decrement N by val N -= val; // Push the num in the // vector res res.push(num); } // Print the vector res for(var i = 0;i<res.length;i++){ document.write(parseInt(Math.pow(2, res[i]))+ " "); }}function countSetBits(x){ var setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;}var N = 7, K = 4;// Function CallnAsKPowersOfTwo(N, K); // This code is contributed by SoumikMondal</script> |
Output:
4 1 1 1
Time Complexity: O(32)
Auxiliary Space: O(1)
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!
