Given a number N, the task is to build N blocks from 1 block by performing following operation:
- Double the number of blocks present in the container and cost for this operation is X.
- Increase the number of blocks present in the container by one and cost for this operation is Y.
- Decrease the number of blocks present in the container by one and cost for this operation is Z.
Examples:
Input: N = 5, X = 2, Y = 1, Z = 3
Output: 4
Explanation:
In the first operation just increase the number of blocks by one, cost = 1 and block count = 2
In the second operation double the blocks, cost = 3 and block count = 4
In the third operation again increase the number_of_blocks by one, cost = 4 and block count = 5
So minimum cost = 4
Input: N = 7, X = 1, Y = 7, Z = 2
Output: 5
Approach:
- Let f(i) denotes minimum cost to build i blocks. So f(i) = min(f(2*i)+X, f(i-1)+Y, f(i+1)+Z) Here current value depends on its next value as well as its previous value but you know that in dynamic programming current value depends only on its previous value. So try to convert its next value to its previous value. We can write f(2*i) as f(i/2) because when we have already built i/2 blocks then we can either double the number of current blocks or increase number of blocks by 1 or decrease number of blocks by 1. Here no need to calculate f(2*i).
Now
f(i) = min(f(i/2)+X, f(i-1)+Y, f(i+1)+Z)
- If i is even then (i+1) must be odd. We can build (i) blocks only by performing the increment operation and the double operation, so you don’t need to perform the decrement operation why? This is because (i+1) is odd number.So if you build (i+1) blocks by performing increment operation then it is confirmed that we have already built i blocks which means we have the minimum cost of building i blocks.If we perform any other operation it must increase your optimal cost which is irrelevant. So recurrence relation when i is even:
f(i)=min(f(i/2)+X, f(i-1)+Y)
- If i is odd then (i+1) must be even. We can build (i+1) blocks only by performing double operation or decrement operation why not increment operation? This is because if you have already built i blocks then no need to build (i+1) blocks because it will add more cost. So we can calculate f(i+1)=f((i+1)/2)+ X. So recurrence relation when i is odd:
f(i)=min(f(i-1)+Y, f( (i+1)/2)+X+Z)
Below is the implementation of the above approach:
C++
// C++ program to Minimum cost // to build N blocks from one block #include <bits/stdc++.h> using namespace std; // Function to calculate // min cost to build N blocks int minCost(int n, int x, int y, int z) { int dp[n + 1] = { 0 }; // Initialize base case dp[0] = dp[1] = 0; for (int i = 2; i <= n; i++) { // Recurrence when // i is odd if (i % 2 == 1) { dp[i] = min( dp[(i + 1) / 2] + x + z, dp[i - 1] + y); } // Recurrence when // i is even else { dp[i] = min(dp[i / 2] + x, dp[i - 1] + y); } } return dp[n]; } // Driver code int main() { int n = 5, x = 2, y = 1, z = 3; cout << minCost(n, x, y, z) << endl; return 0; } |
Java
// Java program to Minimum cost // to build N blocks from one block class GFG { // Function to calculate // min cost to build N blocks static int minCost(int n, int x, int y, int z) { int dp[] = new int[n + 1]; // Initialize base case dp[0] = dp[1] = 0; for (int i = 2; i <= n; i++) { // Recurrence when // i is odd if (i % 2 == 1) { dp[i] = Math.min( dp[(i + 1) / 2] + x + z, dp[i - 1] + y); } // Recurrence when // i is even else { dp[i] = Math.min(dp[i / 2] + x, dp[i - 1] + y); } } return dp[n]; } // Driver code public static void main(String[] args) { int n = 5, x = 2, y = 1, z = 3; System.out.print(minCost(n, x, y, z) +"\n"); } } // This code is contributed by Rajput-Ji |
Python
# python3 program to Minimum cost # to build N blocks from one block # Function to calculate # min cost to build N blocks def minCost(n, x, y, z): dp = [0] * (n + 1) # Initialize base case dp[0] = dp[1] = 0 for i in range(2, n + 1): # Recurrence when # i is odd if (i % 2 == 1): dp[i] = min(dp[(i + 1) // 2] + x + z, dp[i - 1] + y) # Recurrence when # i is even else: dp[i] = min(dp[i // 2] + x, dp[i - 1] + y) return dp[n] # Driver code n = 5x = 2y = 1z = 3print(minCost(n, x, y, z)) # This code is contributed by mohit kumar 29 |
C#
// C# program to Minimum cost // to build N blocks from one block using System; class GFG { // Function to calculate // min cost to build N blocks static int minCost(int n, int x, int y, int z) { int []dp = new int[n + 1]; // Initialize base case dp[0] = dp[1] = 0; for (int i = 2; i <= n; i++) { // Recurrence when // i is odd if (i % 2 == 1) { dp[i] = Math.Min( dp[(i + 1) / 2] + x + z, dp[i - 1] + y); } // Recurrence when // i is even else { dp[i] = Math.Min(dp[i / 2] + x, dp[i - 1] + y); } } return dp[n]; } // Driver code public static void Main(String[] args) { int n = 5, x = 2, y = 1, z = 3; Console.Write(minCost(n, x, y, z) +"\n"); } } // This code is contributed by PrinciRaj1992 |
Javascript
// JavaScript program to calculate the minimum cost// to build N blocks from one blockfunction minCost(n, x, y, z) { let dp = new Array(n + 1).fill(0); // Initialize base case dp[0] = dp[1] = 0; for (let i = 2; i <= n; i++) { // Recurrence when i is odd if (i % 2 === 1) { dp[i] = Math.min(dp[(i + 1) / 2] + x + z, dp[i - 1] + y); } // Recurrence when i is even else { dp[i] = Math.min(dp[i / 2] + x, dp[i - 1] + y); } } return dp[n];}let n = 5, x = 2, y = 1, z = 3;console.log(minCost(n, x, y, z)); |
Output :
4
Time complexity : O(N)
Space complexity : O(N) as a dp array of size N+1 is used.
Efficient approach : Space optimization
The previous implementation uses an array of size n+1 to store the minimum cost to build each number of blocks up to n. but we only need to keep track of the previous two minimum costs in order to compute the current minimum cost. Therefore, we can use just two variables to solve the problem.
Implementation steps:
- Initialize two variables prev1 and prev2 to store the minimum costs for the previous two blocks, both set to 0 initially.
- Loop from i = 2 to n.
- Inside the loop, check if i is odd or even.
- If i is odd, set the current cost cur to the minimum of prev1 + x + z and prev2 + y.
- If i is even, set cur to the minimum of prev1 + x and prev2 + y.
- Update prev1 to be equal to prev2.
- Update prev2 to be equal to cur.
- Return prev2 after the loop has completed. This will be the minimum cost to build n blocks.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;int minCost(int n, int x, int y, int z){ // Initialize base case int prev1 = 0, prev2 = 0; // iterate to get the computation of subproblmes for (int i = 2; i <= n; i++) { // to store current computation int cur; if (i % 2 == 1) { cur = min(prev1 + x + z, prev2 + y); } else { cur = min(prev1 + x, prev2 + y); } // assigning values to iterate further prev1 = prev2; prev2 = cur; } // return answer stored in prev2 return prev2;}// Driver Codeint main(){ int n = 5, x = 2, y = 1, z = 3; cout << minCost(n, x, y, z) << endl; return 0;} |
Python3
def minCost(n: int, x: int, y: int, z: int) -> int: # Initialize base case prev1 = 0 prev2 = 0 # iterate to get the computation of subproblems for i in range(2, n + 1): # to store current computation if i % 2 == 1: cur = min(prev1 + x + z, prev2 + y) else: cur = min(prev1 + x, prev2 + y) # assigning values to iterate further prev1 = prev2 prev2 = cur # return answer stored in prev2 return prev2# Driver Coden = 5x = 2y = 1z = 3print(minCost(n, x, y, z)) |
Javascript
function minCost(n, x, y, z) { // Initialize base case let prev1 = 0, prev2 = 0; // Iterate to get the computation of subproblems for (let i = 2; i <= n; i++) { // To store current computation let cur; if (i % 2 == 1) { cur = Math.min(prev1 + x + z, prev2 + y); } else { cur = Math.min(prev1 + x, prev2 + y); } // Assigning values to iterate further prev1 = prev2; prev2 = cur; } // Return answer stored in prev2 return prev2;}let n = 5, x = 2, y = 1, z = 3;console.log(minCost(n, x, y, z)); |
Output:
4
Time complexity : O(N)
Auxiliary Space : O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
