Python program to represent n as the sum of exactly k power of 2
In this article, we will learn to represent n as the sum of exactly k power 2 in Python.
Examples
Input: n = 6, k = 2 Output: 2 4 Explanation: 2, 4 are both power of 2 and sum is 2 + 4 = 6 Input: n = 5, k = 1 Output: Not possible
Represent n as the sum of exactly k power of 2 in Python
1. Create an array arr[] of size k and initialize its values to 1.
2. Declare a variable s = k.
3. Now start from the last element of the arr[]
- If s+arr[i] <= n then update s += arr[i], arr[i] = arr[i]*2.
- Else, skip the current element.
4. If s is not equal to n print not possible.
5. Else print values stored in the arr[].
def powerTwoElements(n, k): s = k arr = [1 for i in range(k)] i = k-1 while(i>=0): while(s+arr[i] <= n): s += arr[i] arr[i] *= 2 i -= 1 if (s!=n): print("Not possible") else: for i in range(k): print(arr[i], end=" ") n = int(input("Enter the n value: ")) k = int(input("Enter the k value: ")) powerTwoElements(n, k)
Output
Enter the n value: 6 Enter the k value: 2 2 4 Enter the n value: 192 Enter the k value: 16 1 1 1 1 1 1 1 1 1 1 1 1 4 16 32 128 Enter the n value: 5 Enter the k value: 1 Not possible
Also, read
Leave a Reply