Minimally Making Change

Question

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 code-golf 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

Answer 1

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!

Answer 2

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))

Answer 3

JavaScript (ES6), 47 45 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.

Answer 4

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)

Answer 5

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. *)

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

Charcoal, 61 51 30 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.