Introduction

If the target amount can be as large as one billion, the textbook dynamic-programming table for coin change is the wrong tool. An array of size target + 1 is too large, and the usual O(target) memory cost becomes the real bottleneck long before runtime does.

The fix is to stop indexing states by every amount. For large targets, you usually need a method based on number theory, residue classes, or a greedy property of the denomination system.

Why Standard Dynamic Programming Fails

For the minimum-coin version of coin change, the classic recurrence is:

dp[x] = min(dp[x - coin] + 1 for coin in coins if coin <= x)

That works well when x is a few thousand or a few million. It does not scale to one billion because it needs memory proportional to the target.

A billion-element table is not a tuning problem. It is the wrong state model.

Before choosing a replacement, do two quick checks:

1from math import gcd
2from functools import reduce
3
4
5def reachable(target, coins):
6    g = reduce(gcd, coins)
7    return target % g == 0
8
9
10print(reachable(1_000_000_000, [6, 10, 15]))

If target is not divisible by the gcd of the denominations, no exact solution exists.

Case 1: Canonical Coin Systems

Some denomination systems are canonical, which means a greedy algorithm already gives the minimum number of coins. Many real currency systems are designed this way.

In that case, the best memory-constrained algorithm is just greedy:

1def greedy_min_coins(target, coins):
2    coins = sorted(coins, reverse=True)
3    used = []
4    count = 0
5
6    for coin in coins:
7        take, target = divmod(target, coin)
8        if take:
9            used.append((coin, take))
10            count += take
11
12    return count, used, target
13
14
15count, used, rem = greedy_min_coins(1_000_000_000, [25, 10, 5, 1])
16print(count)
17print(used)
18print(rem)

This uses constant extra memory and handles huge targets easily.

The catch is correctness. Greedy is not valid for arbitrary coin sets. For example, with coins [1, 3, 4], greedy makes 6 as 4 + 1 + 1, but the optimum is 3 + 3.

Case 2: Arbitrary Denominations with a Residue Graph

For arbitrary denominations, a useful bounded-memory technique is to work modulo the largest coin M instead of tracking every amount from 0 to target.

The idea is:

• keep only M states, one per remainder modulo M
• find the best way to reach each remainder
• once the correct remainder is reached, fill the rest with copies of the largest coin

To make this work for the minimum-coin problem, minimize the score M * coins_used - total_sum. That score stays unchanged when you add one more M coin, so it captures exactly the part of the solution that matters before the final fill step.

Here is a compact implementation:

1import heapq
2from math import gcd
3from functools import reduce
4
5
6def min_coins_large_target(target, coins):
7    g = reduce(gcd, coins)
8    if target % g != 0:
9        return None
10
11    coins = sorted(set(c // g for c in coins))
12    target //= g
13    M = coins[-1]
14
15    best_score = [10**18] * M
16    best_sum = [10**18] * M
17    pq = [(0, 0, 0)]  # score, sum, residue
18    best_score[0] = 0
19    best_sum[0] = 0
20
21    while pq:
22        score, total, r = heapq.heappop(pq)
23        if score != best_score[r] or total != best_sum[r]:
24            continue
25
26        for coin in coins:
27            nr = (r + coin) % M
28            ns = score + (M - coin)
29            nt = total + coin
30
31            if ns < best_score[nr] or (ns == best_score[nr] and nt < best_sum[nr]):
32                best_score[nr] = ns
33                best_sum[nr] = nt
34                heapq.heappush(pq, (ns, nt, nr))
35
36    residue = target % M
37    if best_sum[residue] > target:
38        return None
39
40    return (target + best_score[residue]) // M
41
42
43print(min_coins_large_target(10, [1, 3, 4]))
44print(min_coins_large_target(1_000_000_000, [6, 9, 20]))

This uses O(M) memory instead of O(target). That can be a dramatic reduction when target is huge and the largest denomination is moderate.

When This Strategy Is a Good Fit

The residue-graph method is useful when:

• coins are unbounded
• you need an exact answer
• target values are huge
• denomination magnitudes are much smaller than the target

It is not ideal if the largest denomination is itself enormous, because the state count becomes M. In that situation, you may need a problem-specific shortcut, a meet-in-the-middle strategy, or proof that the coin system is canonical and therefore greedy.

For production code, it is a good idea to validate the residue-based solver against a normal DP on small targets during testing. The large-target method is compact, but it is also more subtle than the standard recurrence.

Common Pitfalls

The biggest mistake is assuming that greedy always works. It only works for specific coin systems, not for arbitrary denomination sets.

Another mistake is trying to compress the normal DP table slightly and hoping that will make one-billion targets practical. If the algorithm still depends on every amount from 0 to target, the memory problem has not actually been solved.

People also forget the gcd reachability test. That check is cheap and can reject impossible targets immediately.

Finally, residue-based methods depend heavily on choosing the right modulus and objective. Using the largest denomination and minimizing the adjusted score is what keeps the state space small while still targeting the minimum number of coins.

Summary

• A full DP table is not practical when the target can reach one billion.
• Start with a gcd check to rule out impossible targets.
• Use greedy only when the denomination system is known to be canonical.
• For arbitrary unbounded coins, a residue-graph method can reduce memory from O(target) to O(max_coin).
• Large-target solvers should be cross-checked against ordinary DP on small test cases.
• The right state representation matters more than micro-optimizing the classic algorithm.