Min Cost To Buy N Items

Posted: 26 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

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.

Try Problem