= Solution
For $c\geq2$, use largest-denomination-first <greedy algorithm> steps: for $i=n,n-1,\ldots,1$, take $q_i=\lfloor r/c^i\rfloor$ coins and replace the residual amount $r$ by $r-q_ic^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,\ldots,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. \b[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$.
Back to article page
