Why do we do minus 1 in the money change problem while getting index of lower currency coin.
bool compare (int a, int b)
{
return a <= b ;
}
int lb = lower_bound(coins,coins+n, money,compare) - coins - 1 ;
What is the need of doing minus 1 here ?
lower_bound(coins,coins+n, money,compare) - coins will give the position of required element according to 1 indexed array but we have 0 indexed array(first position of array 0) so we need to subtract it by 1.
@yashuanshu0 if this solves your doubt mark it as resolved.
But in the previous topic to find index without using the comparator, we simply did iterator that we got from lower bound minus the array start iterator. That’s why I am confused. Please explain @Abhinav2604
I guess you have a confusion on how lower_bound works, lower_bound returns the index of first element that is not smaller then than given element.
Eg: arr[]={2,4,6,8,10}
val=5
now int it=lower_bound(arr,arr+5,val)-arr;
(it is equal to 2) position of 6 first element not smaller than 5
if arr[]={2,4,5,6,8}
val=5
now int it=lower_bound(arr,arr+5,val)-arr;
(it is equal to 2) position of 5 first element not smaller than 5
So If our aim is to find the first element not smaller than given value,then there is no need to subtract. But if we are aiming at finding the element just smaller than given element we will need to subtract.
@yashuanshu0 I hope this clears your doubt.
If this resolves your doubt mark it resolved.
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.