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

• Finding the power of a number using recursion in Python
• Python program to check the given number is the power of 2 or not