# Minimally Making Change

This problem is an extension of what happens to me on a regular basis: I have to have $1.00 in coins and have to be able to give change to somebody. I discovered rather quickly that the ideal coins to have were 3 quarters, 1 dime, 2 nickels, and 5 pennies. This is the smallest number of coins (11 total) that allows me to make any number of cents 1-99. ### The Challenge Write a program that, given an integer input $$\x\$$ between 2 and 100 (inclusive), outputs the smallest arrangements of coins that does both of the following: 1. The total value of the coins is $$\x\$$ cents. 2. You can use those same coins to make every number of cents less than $$\x\$$. ### Rules • This is so shortest code (in bytes) wins. • Standard loopholes are forbidden • The output can be a list, a four-digit number, or any reasonable representation of the number of coins needed. These coins must be in either ascending or descending order but they do not need to be clearly denoted, only consistently formatted. • In other words, all of the following are valid: [1, 2, 3, 4] [1 2 3 4] 4321 1 2 3 4 1P 2N 3D 4Q PNNDDDQQQQ. Simply state somewhere whether your output is listed in ascending or descending order; it must be the same order for all outputs. • In the case that an optimal solution has none of a given coin, your output must contain a "0" (or other similar character, so long as it is used exclusively and consistently for "0"). This rule does not apply if you use the PNDQ or QDNP format. • The only coins that exist are the penny, nickel, dime, and quarter, being worth 1, 5, 10, and 25 cents respectively. • An arrangement of coins is considered "smaller" than another if the total number of coins is less; all coins are weighted equally. ### Test Cases x Output (Ascending four-digit number) 2 2000 3 3000 4 4000 5 5000 6 6000 7 7000 8 8000 9 4100 10 5100 11 6100 12 7100 13 8100 14 4200 15 5200 16 6200 17 7200 18 8200 19 4110 20 5110 21 6110 22 7110 23 8110 24 4210 25 5210 26 6210 27 7210 28 8210 29 4120 30 5120 31 6120 32 7120 33 8120 34 4220 35 5220 36 6220 37 7220 38 8220 39 4130 40 5130 41 6130 42 7130 43 8130 44 4230 45 5230 46 6230 47 7230 48 8230 49 4211 50 5211 51 6211 52 7211 53 8211 54 4121 55 5121 56 6121 57 7121 58 8121 59 4221 60 5221 61 6221 62 7221 63 8221 64 4131 65 5131 66 6131 67 7131 68 8131 69 4231 70 5231 71 6231 72 7231 73 8231 74 4212 75 5212 76 6212 77 7212 78 8212 79 4122 80 5122 81 6122 82 7122 83 8122 84 4222 85 5222 86 6222 87 7222 88 8222 89 4132 90 5132 91 6132 92 7132 93 8132 94 4232 95 5232 96 6232 97 7232 98 8232 99 4213 100 5213  • Welcome to Code Golf! Nice challenge. – Redwolf Programs Mar 18 at 22:19 • "In the case that an optimal solution has none of a given coin, your output must contain a 0" -> Does this apply even if our output format is akin to "PNNDDDQQQQ"? Or can we just list the needed coins in that case? – Leo Mar 19 at 2:11 • @Leo Oh darn... and now I'm wondering whether adding that output format was a good idea... Probably for that format, you just don't have to output a 0 or similar character – Medix2 Mar 19 at 3:33 • Curious if you know the time complexity of the fastest algorithm for the general version of this problem: Given any n and an array of denomination values, find the minimal number of coins. – Jonah Mar 19 at 6:05 • @Jonah - change-making is special case of what is known as the knapsack problem in operations research. US coins have the property that the "greedy" algorithm in optimal, but this is not always true. In general, the change-making problem is weakly NP-hard. – Llaves Mar 20 at 22:35 ## 9 Answers # JavaScript (ES6), 57 bytes A significantly shorter version suggested by @tsh, who managed to get rid of the edge case $$\n<9\$$. Returns an array of 4 integers in reverse order (quarters to pennies). n=>[z=(n-=x=(n-4)%5+4)/25-.7|0,(n=n/5-5*z-1)/2|0,n%2+1,x]  Try it online! # Original version, 73 bytes Returns an array of 4 integers. n=>n<9?[n,0,0,0]:[x=4-~n%5,y=(z=n/25-.96|0)+(n-=x)/5&1||2,n/5-y-z*5>>1,z]  Try it online! • 63 bytes: n=>[x=(n-4)%5+4,y=((n-=x)/5+~(z=n/25-.7|0))%2+1,n/5-y-z*5>>1,z] – tsh Mar 19 at 3:42 • 57 bytes: n=>[z=(n-=x=(n-4)%5+4)/25-.7|0,(n=n/5-5*z-1)/2|0,n%2+1,x] (output reversed) – tsh Mar 19 at 5:57 • What method or methods are you both using to find the formulas to compress the output table? – Jonah Mar 19 at 6:07 • @Jonah first find patterns for 1cent coins. It loops from 4 to 8 except first few items. You may somehow find a formula for it. Remove these cents from your input (for example, your input is 42, and we know 7 cents already used, only 35 cents left). You will find out if two input get same value after remove these 1 cent coins, they also yield same result for number of other coins. And till now, there are only 20 testcases you need to handle. Try to find patterns for 5 cents, 10 cents, 25 cents coins. You will find out that pattern for 25 cents coins is most easy one to work on. (...) – tsh Mar 19 at 6:17 • (...) So find formula for it. And repeat do the same thing as above steps. That's all you need to come up these formula. – tsh Mar 19 at 6:18 # Excel, 106 bytes =IF(A1<9,A1*1000,LET(p,MOD(A1+1,5)+4,b,(A1-p)/5-1,q,(b>2)*INT((b-3)/5),c,b-5*q,p&(MOD(c,2)+1)&INT(c/2)&q))  ## JavaScript (ES6), 4745 44 bytes f= n=>[25,10,5,1].map(v=>(n-=v*=c=-~n/v-1|0,c)) <input type=number min=2 max=100 oninput=o.textContent=f(this.value)><pre id=o> Port of my latest Charcoal answer, so outputs in reverse order. # Jelly (cairdcoinheringaahing's fork), 23 19 bytes ŒṗŒP§ḟ@ɗƥRḟƥ“¢¦½ı‘Ṫ  Extremely inefficient, and probably also bad in terms of golf. The highest number I could test it on is 18. Outputs a list of the needed coins in ascending order. The naive conversion to Jelly would be +2 bytes. You can Try it online! -4 bytes by changing the output format ## Explanation ŒṗŒP§ḟ@ɗƥRḟƥ“¢¦½ı‘Ṫ Main monadic link Œṗ Integer partitions, sorted from longest to shortest ƥ Keep those where the result is empty: ɗ ( ŒP Power set § Sum each sublist ḟ@ Remove the resulting numbers R from the range [1..input] ɗ ) ƥ Keep those where the result is empty: ḟ Filter out “¢¦½ı‘ [1,5,10,25] Ṫ Tail (last item)  # Wolfram Language (Mathematica), 90 87 bytes MinimalBy[Length@Expand@Exp[Log[1+$^d].#]>#.d&&#&/@FrobeniusSolve[d={1,5,10,25},#],Tr]&


Try it online!

FrobeniusSolve[d={1,5,10,25},#]     (* Find nonnegative integer vectors s where {1,5,10,25}.s==x. *)
Length@Expand@                      (* If the number of terms in the expansion of *)
Exp[Log[1+$^d].s] (* (1+$)^s1(1+$^5)^s2(1+$^10)^s3(1+$^25)^s4 *) >#.d&&#&/@ % (* for each s is not greater than x (=x+1), discard it. *) MinimalBy[ % ,Tr]& (* Select the s with the least sum. *)  # Retina 0.8.2, 80 71 bytes .+$*
(1{25}(?=1{24}))*(1{10}(?=1{9}))*(1{5}(?=1{4}))*(1+)
$.4$#3$#2$#1


Try it online! Link includes test suite that automatically generates numbered results ranging from 2 to the input value. Explanation:

.+
$*  Convert to unary. (1{25}(?=1{24}))*  Match quarters, but leaving at least 24 cents. (1{10}(?=1{9}))*  Match dimes, but leaving at least 9 cents. (1{5}(?=1{4}))*  Match nickels, but leaving at least 4 cents. (1+)  Match the remaining cents. $.4$#3$#2$#1  Output the remaining cents, plus the number of nickels, dimes and quarters. 38 bytes if outputting a list of coin values is acceptable: .+$*
M!1(1{24}|1{9}|1{4}|)(?=\1)
%1


Try it online! No test suite yet. Explanation:

.+
\$*


Convert to unary.

M!1(1{24}|1{9}|1{4}|)(?=\1)


Try all coin values in descending order. For each coin value, ensure that there are enough cents left for one less than that value.

%1


Convert to decimal.

# Wolfram Language (Mathematica), 98 bytes

Counts@Join[h={1,5,10,25},FirstCase[IntegerPartitions[#,#,h],s_/;Tr[1^Union[Tr/@Subsets@s]]>#]]-1&


Try it online!

-13 bytes from @att

• 79 bytes – att Mar 19 at 6:33
• @att nice! Although I had to add the Count since "your output must contain a "0" " – ZaMoC Mar 19 at 11:41
• It seems to be a valid output format (see comments on the main post), but this output method can still go down to 98 bytes – att Mar 19 at 17:39

# Brachylog, 23 bytes

Quite inefficient, TIO only reaches 15.

~+{1|5|10|25}ᵐ.&⟦~{⊇+}ᵛ


Try it online!

~+{1|5|10|25}ᵐ.&⟦~{⊇+}ᵛ
~+                         A list of numbers (which sum is the input)
{1|5|10|25}ᵐ             where each number is 1, 5, 10, or 25
.            is the output.
&⟦          For [0,1,…,N]:
~{⊇+}ᵛ    every element is the sum of a subset of the output.


# Charcoal, 615130 29 bytes

ＮθＦ⟦²⁵χ⁵¦¹⟧«≔÷↔⁻ι⊕θιηＩη≧⁻×ιηθ


Try it online! Link is to verbose version of code. Edit: Reversed the order in which coins are printed to save bytes. Explanation:

Ｎθ


Input x.

Ｆ⟦²⁵χ⁵¦¹⟧«


Loop over all the denominations in descending order. (Charcoal's predefined c variable for 10 conveniently avoids two of the separators here.)

≔÷↔⁻ι⊕θιη


Find how many coins I can use. Unless the original input was less, we need to be able to form an amount one less than this coin's value, so we take the absolute difference from this value (which handles inputs less than the value of the coin) before integer dividing by the coin's value.

Ｉη


Print that number.

≧⁻×ιηθ


Subtract the value of the coins.