Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 7 / e / Solution

Use greedy coin change for powers of an integer, with integer $p\ge 2$. In any optimal solution, there can be no $p$ or more stamps of denomination $p^j$ for $j<k$: replacing $p$ of them by one stamp $p^{j+1}$ preserves value and reduces the stamp count by $p-1$.

Consequently each lower-denomination count lies in $\{0,\dots ,p-1\}$, and their total value is at mostThe number of largest stamps must therefore be $\lfloor m/p^k\rfloor$, leaving a residual below $p^k$. Apply the same argument successively to lower powers. This forces exactly the greedy quotients, proving optimality. For $k=0$, only unit stamps are available and the conclusion is immediate. Integer $p$ is essential to the carry argument and follows from the stated integer denominations whenever denomination $p$ is present.