Let An = { a1, a2, ..., an } be a finite set of distinct cointypes (e.g., a1= 50 cents, a2= 25 cents, a3= 10 cents etc.). Weassume each ai is an integer and that a1 > a2 > ... > an. Eachtype is available in unlimited quantity. The coin changingproblem is to make up an exact amount C using a minimumtotal number of coins. C is an integer > 0.(a) Explain that if an != 1 then there exists a finite set of cointypes and a C for which there is no solution to the coinchanging problem.(b) When an = 1 a greedy solution to the problem will makechange by using the coin types in the order a1, a2, ..., an.When coin type ai is being considered, as many coins of thistype as possible will be given. Write an algorithm based onthis strategy.(c) Give a counterexample to show that the algorithm in (b)doesn\'t necessarily generate solutions that use the minimumtotal number of coins.d) Show that if An = { kn-1, kn-2, ..., k0 } for some k > 1then the greedy method in (b) always yields solutions with aminimum number of coins