Thanksgiving Coin Change

Problem Description

Every Thanksgiving, families gather for a festive dinner and sometimes need to split shared expenses in a fun way. One common problem is making the exact payment using a limited number of coins. In this problem, you are given an array of coin denominations (e.g. [25, 10, 5, 1]), sorted in descending order, and an integer representing the total amount you need to achieve. Your task is to determine the minimum number of coins needed to make the exact amount using a greedy strategy. If it is not possible to form the exact amount with the given coins, return -1.

Requirements

• Write a function thanksgivingCoinChange(coins, amount) (or its equivalent in your language) that takes in:
  • coins: a list/array of integers representing coin denominations in descending order (assume they form a canonical coin system where the greedy algorithm is optimal).
  • amount: an integer representing the target amount.
• Return the minimum number of coins needed to reach the target amount.
• Use a greedy algorithm to solve the problem.
• If it is impossible to form the target amount from the given coins, return -1.

Hint: Start picking the largest coin denomination that does not exceed the remaining amount and subtract it from the amount until you reach zero.

Happy coding and have a wonderful Thanksgiving!