HackerRank Recycling cartridges

general
, ,
1

The following question has been asked in coding test of Atlassian, Cloudera, IBM
People say to use binary Search I can’t see how. Could community please explain it to me and provide with code if possible. This question does not have solution over Internet

You have four input parameters:

Cartridges, Dollars, recycleReward, perksCost.

One has two options:

  1. Recycle one cartridge and get recycleReward amount of dollars
  2. Combine one cartridge and perksCost amount to get a perk item.

we need to maximise the perk items one can buy.

ex: 10, 10, 2, 2

Initially there are 10 cartridges, 10 dollars with the person.
If the persone recycles 3 cartridges he has 7 cartridges and 16 dollars (10 initial + 3*2(recycleReward)).

we can combine 7 cartridges and 14 dollars to buy 7 perk items(as each item costs 1 cartridge and 2 dollars(perksCost)).

1<= cartridges, dollars, recycleReward, perksCost <= 10^9;
allowed time : 2s

1 Like
2

The way binary search is used for such problems is because the below statement holds true.

If we can make X objects with the given amount of resources, then we can also make 0,1,2,…,X-1 objects with the same amount of resources.

This statement is valid for the given problem.

Below is the code that solves this problem. Let me know if it’s not clear.

#include <bits/stdc++.h>
using namespace std;

int Cartridges, Dollars, recycleReward, perksCost;

bool possible(int x)
{
	long long int extra_dollars_needed = x*1ll*perksCost-Dollars;
	if(extra_dollars_needed > Cartridges*1ll*recycleReward)	return false;
	if(extra_dollars_needed<0)  extra_dollars_needed=0;
	Cartridges-=(extra_dollars_needed/recycleReward)+(extra_dollars_needed%recycleReward!=0);
	
	if(Cartridges>=x)	return true;
	else				return false;
}

int main()
{
	cin>>Cartridges>>Dollars>>recycleReward>>perksCost;
	
	int low = 0;		//the minimum possible perks
	int hig = 1e9+1;	//the maximum possible perks
	
	while(low+1<hig)
	{
		int mid = (low+hig);
		mid = mid>>1;
		
		if(possible(mid))
		{
			low=mid;
		}
		else
		{
			hig=mid;
		}
		
		//cout<<low<<" "<<hig<<endl;
	}
	
	if(possible(low+1))		cout<<low+1<<endl;
	else					cout<<low<<endl;
}
1 Like