i did not understand what is taught in the video.can anyone explain me ?
Money exchange problem
Hello @dare_devil_007,
In this question, we have to make changes for an amount.
To solve this we have used inbuilt lower_bound function.
To understand the requirement of this comparator you need to understand the lower_bound() function.
It returns an iterator pointing to the first element in the range [first,last) which does not compare less than val i.e. just smaller than the passed value.
But, in this question we want a coin that is either equal to the amount or just smaller(the closet) to it.
Thus, to consider this equal to, sir has written an external comparator.
Usually, the inbuilt comparator of lower_bound check for the condition of x<y.
Thus, returning an iterator to the value less than money.
Here, you are checking for equality also.
It is operating the same way binary search works.
It takes two parameters, one of which is money=100(in your example) and compares other elements(at current mid) with 100, in the way binary search work.
Now, a question may arise:
in the video the function returns the address of 200 when we pass the key as 100? if the lower bound function was comparing <key, it would’ve returned 100 which is not the case?
The comparator returns the address of 100 only.
But when you subtract coins i.e. the address of first element of the array, it gives the position of 100 in the array i.e. 7.
But, you access the elements with the index at which they are present.
Also, the index begins with 0.
So, the relationship between index and position of an element in an array is, index=position-1
This to get the index of 100 we are then subtracting 1 from the position obtained i.e. 7-1=6.
So, arr[6] is 100, not 200.
- for money=100, lower_bound(coins,coins+n,money,compare) function will give 7 as output because it is present at 7th position.
so finally, lb=7-0-1=6 coins [6]=100.
Suggestion:
Try to print lower_bound(coins,coins+n,100,compare)-coins. - Usually, the inbuilt comparator of lower_bound check for the condition of x<y.
Thus, returning an iterator to the value less than money.
Here, you are checking for equality also.
It is operating the same way binary search works.
It takes two parameters, one of which is money=100(in your example) and compares other elements(at current mid) with 100, in the way binary search work.
Hope, this would help.
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.