Last Updated: 26 Nov, 2020
Min Cost To Buy N Items
Easy
Asked in companies
Ninja Yuki is in the mood of shopping ninja blades today, and why should he not be, its finally the time for the Spring Fair in his Village. Initially, he has 0 number of blades and aims to buy ‘N’ of them from the fair. But the blade shopkeeper being a cunning man himself, presents a weird way of pricing the number of ninja blades Yuki can buy.
Suppose at any instance Yuki has ‘K’ number of blades, then:
1) Yuki can buy 1 more blade with cost 'A.’ He now has ‘K+1’ Ninja blades.
2) Yuki could buy a ‘K’ number of blades with cost 'B.’ He now has ‘2*K’ blades.
where 'A' and 'B' are predefined and constant.
Yuki does not want to get robbed in the fair. Being his nerd friend can you tell him the minimum price he needs to pay to buy exactly ‘N’ ninja blades, considering he has 0 blades initially?
Note:
There can be two or more ways with the exact cost. You can consider any one of them, but the overall cost to reach from 0 to 'N' must be minimized.
For example:
Consider Yuki need to buy 5 blades, the cost of adding 1 blade is 2, and the cost of doubling the blades is 1 then you have to perform the following operations:
1) Doubling 0 will result in 0 only, so add 1 blade to 0 blades with cost 2. Total cost becomes 2.
2) Next, you can either double 1 to reach 2 or add 1 blade. But since the cost of doubling is less than that of adding, so double 1 with cost 1. Total cost becomes 3.
3) Doubling 2 will result in 4 with a cost of 1. Total becomes 4.
4) Adding 1 in 4 will result in 5 (which is the desired number) with a cost of 2. The total cost to reach 5 becomes 6.
Input Format:
The first line of input contains an integer 'T' representing the number of the test cases. Then the test case follows.
The first line of each test case contains three space-separated integers, 'N', 'A', and 'B'. where 'N' is the number of blades Yuki wants to buy, 'A' is the price to increase the number of blades by 1 and 'B' is the price to double the number of blades he has.
Output Format:
For each test case, return the minimum price needed to buy the ‘N’ blades following the method described above.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= 'N' <= 10^4
0 <= 'A','B' <= 10^3
Time limit: 1 second
Approaches
One observation we need to make is that Ninja buys the blades step by step i.e first he buys 1 blade then maybe buys another blade to now have net 2 blades, then again maybe doubles it to buy 4 blades, and so on. That is, we need to compute the answer step by step. For the final price to be minimum we also need the pre-final prices to be minimum.
Following that we can conclude that to get N blades at the minimum price we need to optimally buy either N-1 blade or N/2 blades(assuming N is even). Therefore we can divide the problem into subproblems and can compute them with the same function using recursion.
Steps:
- Let’s create a function REACH_N(N, A, B), which will return us the minimum cost to buy N number of blades with cost A and B.
- Recursively call REACH_N for the initial given values of N, A, and B following the below conditions inside the function:
- Let ANS store the answer for the current value of N.
- If N is 1:
- ANS = A.
- Initially, we have 0 blades, so we can buy 1 blade to make our price A. Doubling 0 won’t help as 2*0 = 0.
- Return ANS.
- If N is even:
- Assign ANS = REACH_N(N-1, A, B) + A. We buy N - 1 blade optimally and then buy 1 blade at the price of A coins.
- ANS = min(ANS, REACH_N(N/2, A, B)) + B. We buy N/2 blades optimally and then simply double the number of blades at the price of B coins.
- Return ANS.
- If N is odd:
- Assign ANS = REACH_N(N-1, A, B) + A. We buy N - 1 blade optimally and then buy 1 blade at the price of A coins.
- As N is odd, no number doubles to N, therefore we cannot use price B here.
Return ANS.
In the previous approach, we are calculating the answer for the same values of N again and again. This leads to Overlapping subproblems and we have already seen the Optimal substructure property(How the recurrence relation was found).
Therefore to avoid computing the same values again and again we need to store the answer for each N into an array and later retrieve it.
Steps:
- Like the previous approach, let’s create a function REACH_N(N, A, B), which will return us the minimum cost to buy N number of blades with cost A and B.
- Create an array MEMO, such that MEMO[M] returns the minimum price needed to buy exactly M number of ninja blades. Initially assign -1 to all indices of MEMO.
- Recursively call REACH_N for the initial given values of N, A, and B following the below conditions inside the function:
- Let ANS store the answer for this N.
- If MEMO[N] is not equal to -1, then the answer for this N has been calculated at some previous computation. Therefore, return the value of MEMO[N].
- If N is 1:
- ANS = A.
- Initially, we have 0 blades, so we can buy 1 blade to make our price A. Doubling 0 won’t help as 2*0 = 0.
- Assign MEMO[1] = A.
- Return ANS.
- If N is even:
- Assign ANS = REACH_N(N-1, A, B) + A. We buy N - 1 blade optimally and then buy 1 blade at the price of A coins.
- ANS = min(ANS, REACH_N(N/2, A, B)) + B. We buy N/2 blades optimally and then simply double the number of blades at the price of B coins.
- Assign MEMO[N] = ANS.
- Return ANS.
- If N is odd:
- Assign ANS = REACH_N(N-1, A, B) + A. We buy N - 1 blade optimally and then buy 1 blade at the price of A coins.
- As N is odd, no number doubles to N, therefore we cannot use price B here.
- Assign MEMO[N] = ANS.
- Return ANS.
In the previous approach we used recursion and top-down memoization to find the answer. This approach introduces a iterative bottom-up Dynamic Programming solution.
Steps:
- Create an array DP of size N+1. Initialize the DP[0] = 0 as it takes 0 coins to buy 0 ninja blades.
- Iterate over DP[i] for each 1 <= i <= N:
- Check, if N is even:
- DP[i] is the minimum of DP[i-1] + A and DP[i/2] + B. We can either buy i - 1 blade and then buy 1 blade at the price of A coins or we can optimally buy N/2 blades and double it with the price of B coins.
- Else
- DP[i] is equal to DP[i-1] + A. We can only buy i -1 blades and then buy 1 blade at the price of A coins.
- Check, if N is even:
- Return the value of DP[N].