Dado un entero x y una array arr[], cada elemento de los cuales es una potencia de 2. La tarea es encontrar el número mínimo de potencias enteras de 2 de la array que, cuando se suman, dan x . Si no es posible representar x con los elementos de array dados, imprima -1 .
Ejemplos:
Entrada: arr[] = {2, 4, 8, 2, 4}, x = 14
Salida: 3
14 se puede escribir como 8 + 4 + 2
Entrada: arr[] = {2, 4, 8, 2, 4 }, x = 5
Salida: -1
5 no se puede representar como la suma de los elementos de la array dada.
Enfoque: para cada potencia de 2, calculemos la cantidad de elementos en la array dada con el valor igual a esto. Llamémoslo cnt . Es obvio que podemos obtener el valor x con avidez (porque todos los valores menores de los elementos son divisores de todos los valores mayores de los elementos).
Ahora vamos a iterar sobre todas las potencias de 2 de 30 a 0 . Sea deg el grado actual. Podemos tomar min(x / 2 deg , cnt deg ) elementos con el valor igual a 2 deg . Que sea cur. Agregue cur a la respuesta y reste 2 grados * cur de x. Repita el proceso hasta que la x ya no se pueda reducir. Si después de iterar sobre todas las potencias, x aún no es cero, imprima -1 . De lo contrario, imprime la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum number
// of given integer powers of 2 required
// to represent a number as sum of these powers
int power_of_two(int n, int a[], int x)
{
// To store the count of powers of two
vector<int> cnt(31);
for (int i = 0; i < n; ++i) {
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
++cnt[__builtin_ctz(a[i])];
}
int ans = 0;
for (int i = 30; i >= 0 && x > 0; --i) {
// If current power is available
// in the array and can be used
int need = min(x >> i, cnt[i]);
// Update the answer
ans += need;
// Reduce the number
x -= (1 << i) * need;
}
// If the original number is not reduced to 0
// It cannot be represented as the sum
// of the given powers of 2
if (x > 0)
ans = -1;
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 2, 4, 4, 8 }, x = 6;
int n = sizeof(arr) / sizeof(arr[0]);
cout << power_of_two(n, arr, x);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
static int __builtin_ctz(int a)
{
int count = 0;
for(int i = 0; i < 40; i++)
if(((a >> i) & 1) == 0)
{
count++;
}
else
break;
return count;
}
// Function to return the minimum number
// of given integer powers of 2 required
// to represent a number as sum of these powers
static int power_of_two(int n, int a[], int x)
{
// To store the count of powers of two
Vector<Integer> cnt = new Vector<Integer>();
for (int i = 0; i < 31; ++i)
cnt.add(0);
for (int i = 0; i < n; ++i)
{
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
cnt.set(__builtin_ctz(a[i]),
(cnt.get(__builtin_ctz(a[i]))==null) ?
1 : cnt.get(__builtin_ctz(a[i]))+1);
}
int ans = 0;
for (int i = 30; i >= 0 && x > 0; --i)
{
// If current power is available
// in the array and can be used
int need = Math.min(x >> i, cnt.get(i));
// Update the answer
ans += need;
// Reduce the number
x -= (1 << i) * need;
}
// If the original number is not reduced to 0
// It cannot be represented as the sum
// of the given powers of 2
if (x > 0)
ans = -1;
return ans;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 2, 4, 4, 8 }, x = 6;
int n = arr.length;
System.out.println(power_of_two(n, arr, x));
}
}
// This code is contributed by Arnab Kundu
python
# Python3 implementation of the approach # Function to return the minimum number # of given eger powers of 2 required # to represent a number as sum of these powers def power_of_two( n, a, x): # To store the count of powers of two cnt=[0 for i in range(31)] for i in range(n): # __builtin_ctz(a[i]) returns the count # of trailing 0s in a[i] count = 0 xx = a[i] while ((xx & 1) == 0): xx = xx >> 1 count += 1 cnt[count]+=1 ans = 0 for i in range(30,-1,-1): if x<=0: continue # If current power is available # in the array and can be used need = min(x >> i, cnt[i]) # Update the answer ans += need # Reduce the number x -= (1 << i) * need # If the original number is not reduced to 0 # It cannot be represented as the sum # of the given powers of 2 if (x > 0): ans = -1 return ans # Driver code arr=[2, 2, 4, 4, 8 ] x = 6 n = len(arr) print(power_of_two(n, arr, x)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
static int __builtin_ctz(int a)
{
int count = 0;
for(int i = 0; i < 40; i++)
if(((a >> i) & 1) == 0)
{
count++;
}
else
break;
return count;
}
// Function to return the minimum number
// of given integer powers of 2 required
// to represent a number as sum of these powers
static int power_of_two(int n, int []a, int x)
{
// To store the count of powers of two
int[] cnt = new int[32];
for (int i = 0; i < n; ++i)
{
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
cnt[__builtin_ctz(a[i])] =
cnt[__builtin_ctz(a[i])] ==
0?1 : cnt[__builtin_ctz(a[i])] + 1;
}
int ans = 0;
for (int i = 30; i >= 0 && x > 0; --i)
{
// If current power is available
// in the array and can be used
int need = Math.Min(x >> i, cnt[i]);
// Update the answer
ans += need;
// Reduce the number
x -= (1 << i) * need;
}
// If the original number is not reduced to 0
// It cannot be represented as the sum
// of the given powers of 2
if (x > 0)
ans = -1;
return ans;
}
// Driver code
static void Main()
{
int []arr = { 2, 2, 4, 4, 8 };
int x = 6;
int n = arr.Length;
Console.WriteLine(power_of_two(n, arr, x));
}
}
// This code is contributed by mits
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the minimum number
// of given integer powers of 2 required
// to represent a number as sum of these powers
function power_of_two( n, a, x)
{
// To store the count of powers of two
let cnt = [];
for(let i = 0;i<31;i++)
cnt.push(0);
for (let i = 0; i < n; ++i) {
// __builtin_ctz(a[i]) returns the count
// of trailing 0s in a[i]
let count = 0;
let xx = a[i];
while ((xx & 1) == 0){
xx = xx >> 1
count += 1
}
cnt[count]+=1;
}
let ans = 0;
for (let i = 30; i >= 0 && x > 0; --i) {
// If current power is available
// in the array and can be used
let need = Math.min(x >> i, cnt[i]);
// Update the answer
ans += need;
// Reduce the number
x -= (1 << i) * need;
}
// If the original number is not reduced to 0
// It cannot be represented as the sum
// of the given powers of 2
if (x > 0)
ans = -1;
return ans;
}
// Driver code
let arr = [ 2, 2, 4, 4, 8 ], x = 6;
let n = arr.length;
document.write( power_of_two(n, arr, x));
</script>
2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(32), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA