Dados dos números N y K. La tarea es imprimir K números que son potencias de 2 y su suma es N. Imprimir -1 si no es posible.
Ejemplos:
Input: N = 9, K = 4 Output: 4 2 2 1 4 + 2 + 2 + 1 = 9 Input: N = 4, K = 5 Output: -1
Enfoque : se puede seguir el siguiente algoritmo para resolver el problema anterior:
- Si K es menor que el número de bits establecidos en N o mayor que el número N, entonces no es posible.
- Inserte las potencias de dos en los bits establecidos en Priority Queue .
- Iterar en la cola de prioridad hasta que obtengamos K elementos, pop() el elemento superior y
- push() element/2 dos veces en la cola de prioridad nuevamente.
- Una vez que se logran los elementos K, imprímalos.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find k numbers that
// are power of 2 and have sum equal
// to N
#include <bits/stdc++.h>
using namespace std;
// function to print numbers
void printNum(int n, int k)
{
// Count the number of set bits
int x = __builtin_popcount(n);
// Not-possible condition
if (k < x || k > n) {
cout << "-1";
return;
}
// Stores the number
priority_queue<int> pq;
// Get the set bits
int two = 1;
while (n) {
if (n & 1) {
pq.push(two);
}
two = two * 2;
n = n >> 1;
}
// Iterate till we get K elements
while (pq.size() < k) {
// Get the topmost element
int el = pq.top();
pq.pop();
// Push the elements/2 into
// priority queue
pq.push(el / 2);
pq.push(el / 2);
}
// Print all elements
int ind = 0;
while (ind < k) {
cout << pq.top() << " ";
pq.pop();
ind++;
}
}
// Driver Code
int main()
{
int n = 9, k = 4;
printNum(n, k);
return 0;
}
Java
// Java program to find k numbers that
// are power of 2 and have sum equal
// to N
import java.io.*;
import java.util.*;
class GFG
{
// function to print numbers
static void printNum(int n, int k)
{
// Count the number of set bits
String str = Integer.toBinaryString(n);
int x = 0;
for (int i = 0; i < str.length(); i++)
if (str.charAt(i) == '1')
x++;
// Not-possible condition
if (k < x || k > n)
{
System.out.println("-1");
return;
}
// Stores the number
PriorityQueue<Integer> pq =
new PriorityQueue<>(Comparator.reverseOrder());
// Get the set bits
int two = 1;
while (n > 0)
{
if ((n & 1) == 1)
pq.add(two);
two *= 2;
n = n >> 1;
}
// Iterate till we get K elements
while (pq.size() < k)
{
// Get the topmost element
int el = pq.poll();
// Push the elements/2 into
// priority queue
pq.add(el / 2);
pq.add(el / 2);
}
// Print all elements
int ind = 0;
while (ind < k)
{
System.out.print(pq.poll() + " ");
ind++;
}
}
// Driver Code
public static void main(String[] args)
{
int n = 9, k = 4;
printNum(n, k);
}
}
// This code is contributed by
// sanjeev2552
Python
# Python program to find k numbers that
# are power of 2 and have sum equal
# to N
# function to print numbers
def printNum(n, k):
# Count the number of set bits
x = 0
m = n
while (m):
x += m & 1
m >>= 1
# Not-possible condition
if k < x or k > n:
print("-1")
return
# Stores the number
pq = []
# Get the set bits
two = 1
while (n):
if (n & 1):
pq.append(two)
two = two * 2
n = n >> 1
# Iterate till we get K elements
while (len(pq) < k):
# Get the topmost element
el = pq[-1]
pq.pop()
# append the elements/2 into
# priority queue
pq.append(el // 2)
pq.append(el // 2)
# Print all elements
ind = 0
pq.sort()
while (ind < k):
print(pq[-1], end = " ")
pq.pop()
ind += 1
# Driver Code
n = 9
k = 4
printNum(n, k)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to find k numbers that
// are power of 2 and have sum equal
// to N
using System;
using System.Collections.Generic;
public class GFG {
// function to print numbers
static void printNum(int n, int k)
{
// Count the number of set bits
int x = 0;
int m = n;
while (m > 0) {
x += m & 1;
m >>= 1;
}
// Not-possible condition
if (k < x || k > n) {
Console.WriteLine("-1");
return;
}
// Stores the number
List<int> pq = new List<int>();
// Get the set bits
int two = 1;
while (n > 0) {
if ((n & 1) != 0)
pq.Add(two);
two = two * 2;
n = n >> 1;
}
// Iterate till we get K elements
while (pq.Count < k) {
// Get the topmost element
int el = pq[pq.Count - 1];
pq.RemoveAt(pq.Count - 1);
// append the elements/2 into
// priority queue
pq.Add(el / 2);
pq.Add(el / 2);
}
// Print all elements
int ind = 0;
pq.Sort();
while (ind < k) {
Console.Write(pq[pq.Count - 1] + " ");
pq.RemoveAt(pq.Count - 1);
ind += 1;
}
}
// Driver code
public static void Main(string[] args)
{
int n = 9;
int k = 4;
printNum(n, k);
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript program to find k numbers that
// are power of 2 and have sum equal
// to N
// function to print numbers
function printNum(n, k)
{
// Count the number of set bits
let x = 0
let m = n
while (m){
x += m & 1
m >>= 1
}
// Not-possible condition
if(k < x || k > n){
document.write("-1","</br>")
return
}
// Stores the number
let pq = []
// Get the set bits
let two = 1
while (n){
if (n & 1)
pq.push(two)
two = two * 2
n = n >> 1
}
// Iterate till we get K elements
while (pq.length < k){
// Get the topmost element
let el = pq[pq.length -1]
pq.pop()
// push the elements/2 into
// priority queue
pq.push(Math.floor(el / 2))
pq.push(Math.floor(el / 2))
}
// Print all elements
let ind = 0
pq.sort()
while (ind < k){
document.write(pq[pq.length -1]," ")
pq.pop()
ind += 1
}
}
// Driver Code
let n = 9
let k = 4
printNum(n, k)
// This code is contributed by shinjanpatra
</script>
Producción:
4 2 2 1
Complejidad de tiempo: O (N * logN), ya que estamos usando un bucle para atravesar N veces y en cada recorrido estamos usando la operación de cola de prioridad que costará logN tiempo.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la cola de prioridad.
Representa n como la suma de exactamente k potencias de dos | conjunto 2