Representar N como la suma de exactamente K potencias de dos | conjunto 3

Dados dos números 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” . Si existen múltiples respuestas, imprima cualquiera.

Ejemplos:

Entrada: N = 5, K = 2
Salida: 4 1
Explicación:
La única forma de representar N como K números que son potencias de 2 es {4, 1}.

Entrada: N = 7, K = 4
Salida: 4 1 1 1
Explicación: 
Las formas posibles de representar N como K números que son potencias de 2 son {4, 1, 1, 1} y {2, 2, 2, 1 }.

Enfoque basado en la cola de prioridad : consulte este artículo para resolver el problema con la cola de prioridad .

Enfoque recursivo : Consulte este artículo para resolver el problema usando Recursion .

Enfoque alternativo: la idea es utilizar el enfoque codicioso para resolver este problema. A continuación se muestran los pasos:

• Inicialice un número entero, digamos num = 31 , y un vector de enteros, digamos res , para almacenar los K números que son potencias de 2 .
• Compruebe si el número de bits en N es mayor que K o si N es menor que K, luego imprima «Imposible».
• Iterar mientras num ≥ 0 y K > 0:
  • Compruebe si N – 2 ^num es menor que K – 1 . Si se encuentra que es cierto, entonces disminuya num en uno y continúe .
  • De lo contrario, disminuya K en uno y N en 2 ^num y empuje num en el vector res .
• Finalmente, imprima el vector res .

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

// 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 2
void 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 Code
int main()
{
    // Given N & K
    int N = 7, K = 4;
 
    // Function Call
    nAsKPowersOfTwo(N, K);
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find K numbers with
// sum N that are powers of 2
static 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 Code
public 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 program for the above approach
 
# Function to find K numbers with
# sum N that are powers of 2
def 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 Code
if __name__ == '__main__':
     
    # Given N & K
    N, K = 7, 4
 
    # Function Call
    nAsKPowersOfTwo(N, K)
 
# This code is contributed mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find K numbers with
// sum N that are powers of 2
static 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 Code
public static void Main(String[] args)
{
    // Given N & K
    int N = 7, K = 4;
 
    // Function Call
    nAsKPowersOfTwo(N, K);
}
}
 
// This code is contributed by shikhasingrajput

<script>
//Javascript program for
//the above approach
 
// Function to find K numbers with
// sum N that are powers of 2
function 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 Call
nAsKPowersOfTwo(N, K);
    
     
// This code is contributed by SoumikMondal
</script>

4 1 1 1

Complejidad de Tiempo: O(32)
Espacio Auxiliar: O(1)