Indian money change problem

#1

#include
#include
using namespace std;
bool compare(int a,int b)
{
return a<=b;
}
int main(){
int coins[]={1,2,5,10,20,50,100,200,500,2000};
int n=sizeof(coins)/sizeof(int);
int money=168;
while(money>0)
{
int lb=lower_bound(coins,coins+n,money,compare)-coins-1;
int m=coins[lb];
cout<<m<<",";
money=money-m;
}
}

In the above code why are we subtracting 1 from the lowerbound when we have the comparator returning lower value everytime.

m must become 6-1=5
and m[5]=50 and not 100.

Please explain .

#2

hey @ujj1804_1156aee80205d0bf
when we use the comparator function, the lower bound function ignores all the values smaller than or equal to the value to be found and hence will always return the index of the key which has a value greater than the value to be found. Hence we will have to subtract 1 from the index in order to get the index of the key which has a value smaller than or equal to the required value.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

Thank you sir , so incase we use comparator the lowerbound function acts as upperbound function , can u also please tell that how the upperbound function work with comparator as compared to when it is used without comparator.

#5

Please reply, so incase we use comparator the lowerbound function acts as upperbound function , can u also please tell that how the upperbound function work with comparator as compared to when it is used without comparator.

#6

@ujj1804_1156aee80205d0bf yes upper bound function will work the same but there is a minor difference, upper bound will not take equal values into consideration it will just give greater value as output.

#7

So incase we have to use upperbound function , in the comparator we will just use a<b and not a<=b as we used in lowerbound function.

#8

@ujj1804_1156aee80205d0bf yes absolutely

1 Like