Minimum cost to form a number X by adding up powers of 2

0 0 4 minutes read

Given an array arr[] of N integers and an integer X. Element arr[i] in array denotes the cost to use 2ⁱ. The task is to find the minimum cost to choose the numbers which add up to X.
Examples:

Input: arr[] = { 20, 50, 60, 90 }, X = 7
Output: 120
2² + 2¹ + 2⁰ = 4 + 2 + 1 = 7 with cost = 60 + 50 + 20 = 130
But we can use 2² + 3 * 2⁰ = 4 + 3 * 1 = 7 with cost = 60 + 3 * 20 = 120 which is minimum possible.
Input: arr[] = { 10, 5, 50 }, X = 4
Output: 10

Approach: The problem can be solved using basic Dynamic Programming. The fact that every number can be formed using powers of 2 has been used here. We can initially calculate the minimal cost required to form powers of 2 themselves. The recurrence will be as follows:

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

Once the array is re-computed, we can simply keep adding the cost according to the set bits in the number X.
Below is the implementation of the above approach:

C++

// 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

// 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 

Python3

# 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#

// 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
 
// 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.
?>

Javascript

<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>

Output:

Time Complexity: O(N + log(x)), as we are using a loop to traverse N times and log(x) times as in every traversal we are right shifting x by 1 bit which will be equivalent to log(x).

Auxiliary Space: O(1), as we are not using any extra space.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!