595. Fewest Coins When Each Divides the Next

A coin system is given as n values in increasing order, where the smallest is 1 and EACH VALUE DIVIDES THE NEXT. Pay an exact amount using as few coins as possible, with an unlimited supply of each.

Print the fewest coins needed.

coins 1 5 25, amount 63 -> 7 two 25s, two 5s, three 1s coins 1 2 4 8, amount 15 -> 4 8 + 4 + 2 + 1

## Why the knapsack is unusable

Problems 486 and 489 solve exactly this with a table over the amount. That table is correct and here the amount reaches 10^18, so it cannot be built at any speed.

This is the same situation as 593: the recurrence is fine and the constraints have moved the table out of reach. What is different is that the extra PROMISE in the statement buys a completely different algorithm.

## Take as many of the largest as possible

for each coin from largest to smallest: used += amount / coin amount = amount % coin

## Why the promise makes it correct

The greedy is NOT correct for coin systems in general. The standard counterexample is 1 3 4 paying 6: greedy takes 4 + 1 + 1 for three coins, and 3 + 3 uses two. Notice that 3 does not divide 4, so that system is outside this problem's promise.

Here is the argument that the promise repairs it. Let the coins be c[0] = 1 < c[1] < ... < c[n-1], with each dividing the next, and take any optimal solution.

Suppose it uses t coins of value c[i] where t * c[i] >= c[i+1]. Since c[i] divides c[i+1], let q = c[i+1] / c[i], which is an integer and at least 2. Then q of those coins can be replaced by a SINGLE c[i+1], using q - 1 fewer coins.

An optimal solution admits no such improvement, so it uses fewer than q coins of each value below the top, and that is exactly the remainder the greedy leaves. The two agree at every level, so the greedy is optimal.

That argument is the whole point of the problem. A greedy without one is a guess, and the divisibility is precisely the hypothesis it needs.

## Always solvable

The smallest coin is 1, so every amount can be paid and there is no impossible case. That is also why no -1 appears in the output.

## Boundaries

An amount of 0 uses no coins. A system of just 1 uses amount coins, which reaches 10^18 and is why the count itself needs 64 bits, not only the amount.

## Cost

Time O(n). Space O(1).

Constraints - `1 ≤ n ≤ 60` - `0 ≤ amount ≤ 10^18` - `c[0] = 1` and `c[i]` divides `c[i+1]` - `c[i] ≤ 10^18`