Give an efficient algorithm and analyze the time and space requirements of your algorithm.

NJIT decides to introduce its own coinage with three different types of coins: 1 cent, 5 cents, and 8 cents. We would like to know what is the minimum number of coins we can use if we pay for an item worth n cents. Give an efficient algorithm that if given n as input, prints as output the minimum set of coins that has a value exactly n. Analyze the time and space requirements of your algorithm. Prove its correctness. For example, you can pay an item worth 40 cents by giving five 8-cent coins; other alternatives are eight 5-cent coins, or forty 1-cent coins, or say four 8-cent, one 5-cent, and three 1-cent coins.