# HackerRank Recycling cartridges

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

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