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:
- Recycle one cartridge and get recycleReward amount of dollars
- 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
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.
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(Cartridges>=x) return true;
else return false;
int low = 0; //the minimum possible perks
int hig = 1e9+1; //the maximum possible perks
int mid = (low+hig);
mid = mid>>1;