The earnings of gold through mining is 'x' units of gold per day. There are 'n' machines available that can be bought and the cost of the ith machine is arr[i] units of gold. It can be decided to buy any machine on any day if there is a sufficient amount of gold to buy that machine and any ith machine can be bought only once. Also, Each machine extracts extra 'z' units of gold per day, i.e. if there are 'j' machines then one can get (x + j * z) units of gold per day. Note that you can buy multiple machines on the same day.
Initially, there is no gold. Find the maximum amount of gold that one can get at the end of 'k' days.
Parameters:
x: an integer denoting units of gold you earn per day
z: an integer denoting units of gold, machine extract per day
arr[arr[0],...arr[n-1]]: An array of integers denoting the costs of all machines
k: an integer denoting the number of days
Example 1:
Input:
x = 1, z = 2, n = 3, arr = [3,2,4], k = 5
Output:
10
Explanation:
Day 1: Earn 1 unit of gold. Current amount of gold = 1
Day 2: Earn 1 unit of gold. Current amount of gold = 2
Day 3: Buy machine 1 at the start of day 3 which cost arr[1] = 2 units of gold. Current amount of gold = 2 — 2 + (1 + 2 x 1) = 3.
Day 4: Buy machine 0 at the start of day 4 which cost arr[0] = 3 units of gold. Current amount of gold = 3 — 3 + (1 + 2 x 2) = 5.
Day 5: Earn 5 units of gold (1 through mining and 4 through 2 machines bought). Final amount of gold = 5 + 5 = 10.
Example 2:
Input:
x = 3, z = 2, n = 3, arr = [4,2,3], k = 4
Output:
17
Explanation:
Day 1: Earn 3 units of gold. Current amount of gold = 3.
Day 2: Buy machine 2 at the start of day 2 which cost arr[2] = 3 units of gold. Current amount of gold = 3 — 3 + (3 + 2 x 1) = 5.
Day 3: Buy machine 1 at the start of day 3 which cost arr[1] = 2 units of gold. Current amount of gold = 5 — 2 + (3 + 2 x 2) = 10.
Day 4: Earn 7 units of gold (3 through mining and 4 through 2 machines bought). Final amount of gold = 10 + 7 = 17.
Example 3:
Input:
x = 8, z = 3, n = 3, arr = [7,7,7], k = 2
Output:
16
Explanation:
Day 1: Earn 8 units of gold. Current amount of gold = 8.
Day 2: Earn 8 units of gold (only through mining). Final amount of gold = 8 + 8 = 16
Constraints:
1 <= n <= 10^5
1 <= arr[i] <= 10^5
1 <= x , z <= 10^5
1 <= k <= 10^5
Someone please tell the approach and the solution to this problem.
You can buy a new machine if you have enough money and the machine produces more gold than it costs in the remaining days. Obviously you should pick the cheapest machine first.
Here's an Implementation:
Hey thanks a lot for the solution. But I see that you have not taken into consideration the fact that you can buy multiple machines on the same day depending on whether it will yield you maximum gold on the kth day.
Another point is that buying a machine on ith day can yield maximum gold on ith day but it may not ensure that the yield will be maximum at the end of kth day. Don't you feel that it's kind of a DP problem, where you explore all the paths and return the one that is optimal?
For example: x = 3, z = 3, n = 4, A = [1, 2, 3, 4], k = 2
Day 1: Max gold = 3 Day 2: Buy machine 1 and 2 (A[1] and A[2]) => Max Gold = 3 — (1 + 2) + 3 + 2 x 3 = 9
So on Day 2, the maximum value should be 9 but based on your code, it is coming as 8.
Waiting for your response.
Hi sorry I didn't catch the part where buying multiple machines are allowed on the same day, if that's allowed then simply change the only "if" in the code to "while" and it should work as expected. Also, we buy a machine as long as it returns strictly more gold than what it costs, till the end of the Kth day, signified by the second condition inside the while loop.
Apart from the slightly embarrassing confession that I haven't learnt the first thing about DP, I think this problem is greedy and 2Pointers based. Please test the code after replacing the if with a while and inform me if it's working. It should work unless I am again missing something.
Thanks a lot. It is working as expected after changing if to while and putting j<N as the first condition.
Good to know, may I know the source of this problem?
This question appeared in one of the placement rounds of a company few days ago.