In money change problem

#1

why are we writing lower_bound-coin-1? why do we need to subtract 1?

#2

@Shreya-Gupta-2383169445069382 Lower_bound( ) gives us the position of the element that is not smaller than the given number (focus on not).
So the position returned by lower bound will have element either equal to number or it will be greater than the number.
Now to get the position of element just smaller than number we subtract 1, (as array is sorted in ascending order the previous element must be smaller)
If this resolves your doubt mark it as resolved.

#3

but when we are using our own comparator func. if are putting <= sign in that case we get a no <= to money which is required so there is no need for -1?

#4

@Shreya-Gupta-2383169445069382 comp effects only how we will be partitioning the array. The relation between result and passed value need not to be the same as that of comp function. Infact here it is quite opposite.
Eg

int arr[]={1,2,4,5,6,8,10};
int i=lower_bound(arr,arr+6,5,myComp)-arr;
now if comp function uses <= , arr[i]=6
if comp uses < , arr[i]=5
Here Comp function is used in sol to make sure that returned value is always greater.

#5

i didnot get it ?? coulld u elaborate?

#6

@Shreya-Gupta-2383169445069382 lower_bound will keep moving forward when comp returns true. So if we use <= the return value will always be greater than key. As when for any value =key, our <= will return true, so lower bound will move forward.
So basically the comp function makes sure that the returned position stores a value greater than the key (always)
If this resolved your doubt mark its as resolved.

#7

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.