Representa n como la suma de exactamente k potencias de dos | conjunto 2

Dados dos enteros n y k , la tarea es encontrar si es posible representar n como la suma de exactamente k potencias de 2 . Si es posible, imprima k enteros positivos tales que sean potencias de 2 y su suma sea exactamente igual a n ; de lo contrario, imprima Imposible .
Ejemplos: 
 

Entrada: n = 9, k = 4 
Salida: 1 2 2 4 
1, 2 y 4 son todas potencias de 2 y 1 + 2 + 2 + 4 = 9.
Entrada: n = 3, k = 7 
Salida: Imposible 
Es imposible ya que 3 no se puede representar como la suma de 7 números que son potencias de 2. 
 

Hemos discutido un enfoque para resolver este problema en Encuentra k números que son potencias de 2 y tienen suma N . En esta publicación, se está discutiendo un enfoque diferente.
Acercarse: 
 

• Cree una array arr[] de tamaño k con todos los elementos inicializados en 1 y cree una variable sum = k .
• Ahora a partir del último elemento de arr[] 
  • Si sum + arr[i] ≤ n entonces actualice sum = sum + arr[i] y arr[i] = arr[i] * 2 .
  • De lo contrario, omita el elemento actual.
• Si suma = n , entonces los contenidos de arr[] son ​​los elementos requeridos.
• De lo contrario, es imposible representar n exactamente como k potencias de 2 .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <iostream>
using namespace std;
 
// Function to print k numbers which are powers of two
// and whose sum is equal to n
void FindAllElements(int n, int k)
{
    // Initialising the sum with k
    int sum = k;
 
    // Initialising an array A with k elements
    // and filling all elements with 1
    int A[k];
    fill(A, A + k, 1);
 
    for (int i = k - 1; i >= 0; --i) {
 
        // Iterating A[] from k-1 to 0
        while (sum + A[i] <= n) {
 
            // Update sum and A[i]
            // till sum + A[i] is less than equal to n
            sum += A[i];
            A[i] *= 2;
        }
    }
 
    // Impossible to find the combination
    if (sum != n) {
        cout << "Impossible";
    }
 
    // Possible solution is stored in A[]
    else {
        for (int i = 0; i < k; ++i)
            cout << A[i] << ' ';
    }
}
 
// Driver code
int main()
{
    int n = 12;
    int k = 6;
 
    FindAllElements(n, k);
 
    return 0;
}

// Java implementation of the above approach
import java.util.Arrays;
 
public class GfG {
     
    // Function to print k numbers which are powers of two
    // and whose sum is equal to n
    public static void FindAllElements(int n, int k)
    {
        // Initialising the sum with k
        int sum = k;
       
        // Initialising an array A with k elements
        // and filling all elements with 1
        int[] A = new int[k];
        Arrays.fill(A, 0, k, 1);
         
        for (int i = k - 1; i >= 0; --i) {
       
            // Iterating A[] from k-1 to 0
            while (sum + A[i] <= n) {
       
                // Update sum and A[i]
                // till sum + A[i] is less than equal to n
                sum += A[i];
                A[i] *= 2;
            }
        }
       
        // Impossible to find the combination
        if (sum != n) {
            System.out.print("Impossible");
        }
       
        // Possible solution is stored in A[]
        else {
            for (int i = 0; i < k; ++i)
                System.out.print(A[i] + " ");
        }
    }
     
    public static void main(String []args){
         
        int n = 12;
        int k = 6;
       
        FindAllElements(n, k);
    }
}
   
// This code is contributed by Rituraj Jain

# Python 3 implementation of the above approach
 
# Function to print k numbers which are
# powers of two and whose sum is equal to n
def FindAllElements(n, k):
     
    # Initialising the sum with k
    sum = k
 
    # Initialising an array A with k elements
    # and filling all elements with 1
    A = [1 for i in range(k)]
    i = k - 1
    while(i >= 0):
         
        # Iterating A[] from k-1 to 0
        while (sum + A[i] <= n):
             
            # Update sum and A[i] till
            # sum + A[i] is less than equal to n
            sum += A[i]
            A[i] *= 2
        i -= 1
     
    # Impossible to find the combination
    if (sum != n):
        print("Impossible")
 
    # Possible solution is stored in A[]
    else:
        for i in range(0, k, 1):
            print(A[i], end = ' ')
 
# Driver code
if __name__ == '__main__':
    n = 12
    k = 6
 
    FindAllElements(n, k)
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the above approach
using System;
 
class GfG
{
     
    // Function to print k numbers
    // which are powers of two
    // and whose sum is equal to n
    public static void FindAllElements(int n, int k)
    {
        // Initialising the sum with k
        int sum = k;
         
        // Initialising an array A with k elements
        // and filling all elements with 1
        int[] A = new int[k];
        for(int i = 0; i < k; i++)
            A[i] = 1;
         
        for (int i = k - 1; i >= 0; --i)
        {
         
            // Iterating A[] from k-1 to 0
            while (sum + A[i] <= n)
            {
         
                // Update sum and A[i]
                // till sum + A[i] is less than equal to n
                sum += A[i];
                A[i] *= 2;
            }
        }
         
        // Impossible to find the combination
        if (sum != n)
        {
            Console.Write("Impossible");
        }
         
        // Possible solution is stored in A[]
        else
        {
            for (int i = 0; i < k; ++i)
                Console.Write(A[i] + " ");
        }
    }
     
    // Driver code
    public static void Main(String []args)
    {
         
        int n = 12;
        int k = 6;
         
        FindAllElements(n, k);
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP implementation of the above approach
 
// Function to print k numbers which are
// powers of two and whose sum is equal to n
function FindAllElements($n, $k)
{
    // Initialising the sum with k
    $sum = $k;
 
    // Initialising an array A with k elements
    // and filling all elements with 1
    $A = array_fill(0, $k, 1) ;
 
 
    for ($i = $k - 1; $i >= 0; --$i)
    {
 
        // Iterating A[] from k-1 to 0
        while ($sum + $A[$i] <= $n)
        {
 
            // Update sum and A[i] till 
            // sum + A[i] is less than equal to n
            $sum += $A[$i];
            $A[$i] *= 2;
        }
    }
 
    // Impossible to find the combination
    if ($sum != $n)
    {
        echo"Impossible";
    }
 
    // Possible solution is stored in A[]
    else
    {
        for ($i = 0; $i < $k; ++$i)
            echo $A[$i], ' ';
    }
}
 
// Driver code
$n = 12;
$k = 6;
 
FindAllElements($n, $k);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the above approach
 
     
// Function to print k numbers which are powers of two
// and whose sum is equal to n
function FindAllElements( n, k)
{
    // Initialising the sum with k
    let sum = k;
         
    // Initialising an array A with k elements
    // and filling all elements with 1
    let A = new Array(k).fill(1);
     
         
    for (let i = k - 1; i >= 0; --i) {
         
        // Iterating A[] from k-1 to 0
        while (sum + A[i] <= n) {
         
            // Update sum and A[i]
            // till sum + A[i] is less than equal to n
            sum += A[i];
            A[i] *= 2;
        }
    }
         
    // Impossible to find the combination
    if (sum != n) {
        document.write("Impossible");
    }
         
    // Possible solution is stored in A[]
    else {
        for (let i = 0; i < k; ++i)
            document.write(A[i] + " ");
    }
}
     
 
// Driver Code
 
let n = 12;
let k = 6;
         
FindAllElements(n, k);
 
</script>

1 1 1 1 4 4 

Complejidad del tiempo: O(k*log ₂ (nk))

Espacio Auxiliar: O(k), ya que se ha tomado k espacio extra.