Please give detailed steps, thank you. 1. [14 POINTS] Problem 9.47 [this problem
ID: 3736492 • Letter: P
Question
Please give detailed steps, thank you.
1. [14 POINTS] Problem 9.47 [this problem is not in the F17 textbook]: A postage dispenser has 4e and 7e stamps. A customer will input n, the desired postage, and the machine should: (a) Determine if postage n can be dispensed (yes or no), and (b) If yes, give a way to dispense the postage: numbers n4 and n7 for which n 4n4+7n Give an algorithm to solve (a) and (b)in O(1) compute-time. Assume basic operations take O(1) time on any inputs (+,-, x, +,1J, -). (Note, dispensing the postage will take linear time.)Explanation / Answer
Considering two stamps of cost 4 cents and 7 cents, we can formulate the possbile values of n for which there exists a solution of dispensing the postage.
4, 7, 8, 11, 12, 14, 15, 16, 18, 19, 20, 21
After these values, for any subsequent n > 21, there always exists a solution where on the basis of mathematical induction step, the solution can be find for n-4 and then just add a 4-cent stamp to the answer.
This problem, thus results out to have a O(1) time-complexity solution.