Minimum Coins to Pay with Overpay and Change Allowed

Problem: Minimum Coins to Pay (Overpay Allowed, Change Given) You have infinitely many coins with denominations 1, 5, 10, 50, 100, 200. You need to pay an amount n to someone. You are allowed to overpay (pay some total p >= n), and the other person will give you change of amount p - n using the same coin denominations (also unlimited). Compute the minimum number of coins you need to use under an optimal strategy (choosing how much to pay and how the change is made). Clarification: the “coins you use” typically counts only the coins you hand over; change coins are given by the other person and are not counted. (Confirm with the interviewer.) Input One integer n. Output One integer: the minimum number of coins you need to pay. Constraints 1 <= n <= 10^9 Example Input 41 Output 3 Explanation One optimal approach: pay 50 + 1 = 51 (2 coins), receive change 10, resulting in net payment 41. Note: If the task counts (coins paid + coins received as change), then the answer for this example would be 3. Example Input 41 Output 2