I will tell you the intuition behind this problem problem statement- Consider a person want to change his money with other denominations as he needs it for his journey. He went to a shop and requests the person to change this sum. The shopkeeper is only having certain denomination’s coins…