Given an array arr[] of N integers and an integer X. Element arr[i] in array denotes the cost to use 2i. 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
22 + 21 + 20 = 4 + 2 + 1 = 7 with cost = 60 + 50 + 20 = 130
But we can use 22 + 3 * 20 = 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 costint 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 codeint 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 approachimport java.io.*;class GFG { // Function to return the minimum coststatic 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 codepublic 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 costdef 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 codeif __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 approachusing System;class GFG { // Function to return the minimum costpublic 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 codepublic 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 costfunction 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> |
120
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!