Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 6 / c / iii

For $c\ge 2$, use largest-denomination-first greedy algorithm steps: for $i=n,n-1,\dots ,1$, take $q_i=\lfloor r/c^i\rfloor$ coins and replace the residual amount $r$ by $r-q_i{c}^i$. A target is representable exactly when it is divisible by $c$, because the smallest denomination is $c$, not one.

To prove optimality whenever the target is representable, observe that an optimum can have fewer than $c$ coins of every denomination $c^i$ with $i<n$: replacing $c$ such coins by one $c^{i+1}$ coin preserves value and reduces the count by $c-1$. After all such carrying, the coefficients of $c,c^2,\dots ,c^{n-1}$ are the unique base-$c$ digits of $v/c$, while the coefficient of $c^n$ is the remaining quotient. Largest-first division produces exactly these coefficients. The greedy coin count is optimal, and can be computed with $O(n)$ quotient/remainder operations without listing every coin.

For $c=1$, distinct denominations permit only $n=1$; then all coins have value one and the answer is $v$. This handles the printed positive-integer condition without silently assuming $c>1$.