Coste mínimo para formar un número X sumando potencias de 2

Dada una array arr[] de N enteros y un entero X . El elemento arr[i] en la array denota el costo de usar 2 ⁱ . La tarea es encontrar el costo mínimo para elegir los números que suman  X.
Ejemplos: 
 

Entrada: arr[] = { 20, 50, 60, 90 }, X = 7 
Salida: 120 
2 ² + 2 ¹ + 2 ⁰ = 4 + 2 + 1 = 7 con costo = 60 + 50 + 20 = 130 
Pero nosotros puede usar 2 ² + 3 * 2 ⁰ = 4 + 3 * 1 = 7 con un costo = 60 + 3 * 20 = 120 que es el mínimo posible.
Entrada: arr[] = { 10, 5, 50 }, X = 4 
Salida: 10 
 

Enfoque: El problema se puede resolver utilizando Programación Dinámica básica . Aquí se ha utilizado el hecho de que todo número se puede formar usando potencias de 2. Inicialmente podemos calcular el costo mínimo requerido para formar potencias de 2. La recurrencia será la siguiente: 
 

a[i] = min(a[i], 2 * a[i – 1])

Una vez que se vuelve a calcular la array, simplemente podemos seguir agregando el costo de acuerdo con los bits establecidos en el número X.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum cost
int MinimumCost(int a[], int n, int x)
{
 
    // Re-compute the array
    for (int i = 1; i < n; i++) {
        a[i] = min(a[i], 2 * a[i - 1]);
    }
 
    int ind = 0;
 
    int sum = 0;
 
    // Add answers for set bits
    while (x) {
 
        // If bit is set
        if (x & 1)
            sum += a[ind];
 
        // Increase the counter
        ind++;
 
        // Right shift the number
        x = x >> 1;
    }
 
    return sum;
}
 
// Driver code
int main()
{
    int a[] = { 20, 50, 60, 90 };
    int x = 7;
    int n = sizeof(a) / sizeof(a[0]);
    cout << MinimumCost(a, n, x);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to return the minimum cost
static int MinimumCost(int a[], int n, int x)
{
 
    // Re-compute the array
    for (int i = 1; i < n; i++)
    {
        a[i] = Math.min(a[i], 2 * a[i - 1]);
    }
 
    int ind = 0;
 
    int sum = 0;
 
    // Add answers for set bits
    while (x > 0)
    {
 
        // If bit is set
        if (x != 0 )
            sum += a[ind];
 
        // Increase the counter
        ind++;
 
        // Right shift the number
        x = x >> 1;
    }
 
    return sum;
}
 
// Driver code
public static void main (String[] args)
{
 
    int a[] = { 20, 50, 60, 90 };
    int x = 7;
    int n =a.length;
    System.out.println (MinimumCost(a, n, x));
}
}
 
// This Code is contributed by akt_mit

# Python 3 implementation of the approach
 
# Function to return the minimum cost
def MinimumCost(a, n, x):
     
    # Re-compute the array
    for i in range(1, n, 1):
        a[i] = min(a[i], 2 * a[i - 1])
 
    ind = 0
 
    sum = 0
 
    # Add answers for set bits
    while (x):
         
        # If bit is set
        if (x & 1):
            sum += a[ind]
 
        # Increase the counter
        ind += 1
 
        # Right shift the number
        x = x >> 1
 
    return sum
 
# Driver code
if __name__ == '__main__':
    a = [20, 50, 60, 90]
    x = 7
    n = len(a)
    print(MinimumCost(a, n, x))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the minimum cost
public static int MinimumCost(int []a, int n, int x)
{
 
    // Re-compute the array
    for (int i = 1; i < n; i++)
    {
        a[i] = Math.Min(a[i], 2 * a[i - 1]);
    }
 
    int ind = 0;
 
    int sum = 0;
 
    // Add answers for set bits
    while (x > 0)
    {
 
        // If bit is set
        if (x != 0 )
            sum += a[ind];
 
        // Increase the counter
        ind++;
 
        // Right shift the number
        x = x >> 1;
    }
 
    return sum;
}
 
// Driver code
public static void Main ()
{
 
    int []a = { 20, 50, 60, 90 };
    int x = 7;
    int n =a.Length;
    Console.WriteLine(MinimumCost(a, n, x));
}
}
 
// This Code is contributed by SoM15242

<?php
 
// PHP implementation of the approach
// Function to return the minimum cost
 
function MinimumCost($a, $n, $x)
{
 
    // Re-compute the array
    for ($i = 1; $i < $n; $i++)
    {
        $a[$i] = min($a[$i], 2 * $a[$i - 1]);
    }
 
    $ind = 0;
 
    $sum = 0;
 
    // Add answers for set bits
    while ($x)
    {
 
        // If bit is set
        if ($x & 1)
            $sum += $a[$ind];
 
        // Increase the counter
        $ind++;
 
        // Right shift the number
        $x = $x >> 1;
    }
 
    return $sum;
}
 
    // Driver code
    $a = array( 20, 50, 60, 90 );
    $x = 7;
    $n = sizeof($a) / sizeof($a[0]);
    echo MinimumCost($a, $n, $x);
 
// This code is contributed by ajit.
?>

<script>
 
// Javascript implementation of the approach
 
    // Function to return the minimum cost
    function MinimumCost(a , n , x) {
 
        // Re-compute the array
        for (i = 1; i < n; i++) {
            a[i] = Math.min(a[i], 2 * a[i - 1]);
        }
 
        var ind = 0;
 
        var sum = 0;
 
        // Add answers for set bits
        while (x > 0) {
 
            // If bit is set
            if (x != 0)
                sum += a[ind];
 
            // Increase the counter
            ind++;
 
            // Right shift the number
            x = x >> 1;
        }
 
        return sum;
    }
 
    // Driver code
     
 
        var a = [ 20, 50, 60, 90 ];
        var x = 7;
        var n = a.length;
        document.write(MinimumCost(a, n, x));
 
// This code contributed by umadevi9616
 
</script>

120

Complejidad de tiempo: O(N + log(x)), ya que estamos usando un bucle para atravesar N veces y log(x) veces, ya que en cada recorrido estamos desplazando x a la derecha en 1 bit, lo que será equivalente a log(x) .

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.