Teaser 3328: Loose change
From The Sunday Times, 5th July 2026 [link] [link]
Elaine reminded Phil to take his suit to the dry cleaners. When Phil emptied his pockets he found he had exactly £5 in coins. All denominations of coin were represented (£2, £1, 50p, 20p, 10p, 5p, 2p and 1p) but there were more of one coin than any other.
Phil told all of this to Elaine, but she couldn’t work out how many coins Phil had. “If I told you the total two-figure number of coins you would be able to work out the numbers of each coin present”, said Phil.
Which denomination appeared most and how many of that coin were present?
The S2T2 site now has all puzzles from April 2009 to present (along with solutions), which is a continuous run of the most recent 900 Teaser puzzles. Additionally there are currently 460 older Teaser puzzles available too.
[teaser3328]
Frits, 
Alex.T.Sutherland, and 1 other are discussing. 
Ruud and 
Tony Smith, 
Alex.T.Sutherland, 
John Crabtree are discussing. 
Jim Randell 7:43 am on 5 July 2026 Permalink |
This Python program runs in 87ms. (Internal runtime is 13ms).
from enigma import (express, group, singleton, printf) # denominations (in increasing order) ds = [1, 2, 5, 10, 20, 50, 100, 200] # generate candidate quantities def generate(): # make a total amount of 500p for qs in express(500, ds, min_q=1): # only allow those with a distinct maximum quantity if qs.count(max(qs)) == 1: yield qs # collect arrangements by total number of coins g = group(generate(), by=sum) # look for unique 2-digit totals for (k, vs) in g.items(): if k < 10 or k > 99: continue qs = singleton(vs) if qs is None: continue # output solution printf("{k} coins = {qs} * {ds}p") # find maximum occurring denomination i = qs.index(max(qs)) printf("-> most common = {q} * {d}p", q=qs[i], d=ds[i])Solution: There were more 20p coins than any other denomination. There were 4 of them.
The solution is derived from the following arrangement:
LikeLike
Ruud 10:55 am on 5 July 2026 Permalink |
import collections coins = (200, 100, 50, 20, 10, 5, 2, 1) def allocate(amount_left, coins_left, result): if coins_left: for n in range(1, amount_left // coins_left[0] + 1): if amount_left >= n * coins_left[0]: yield from allocate(amount_left - n * coins_left[0], coins_left[1:], result + [n]) else: if amount_left == 0 and result.count(max(result)) == 1 and len(str(sum(result))) == 2: yield result collect = collections.defaultdict(list) for coin_count in allocate(500, coins, []): collect[sum(coin_count)].append(coin_count) for number_of_coins, coin_counts in collect.items(): if len(coin_counts) == 1: print(*(f"{number} * {coin}p" for coin, number in zip(coins, coin_counts[0]) if number == max(coin_counts[0]))) print(*(f"{number} * {coin}p" for coin, number in zip(coins, coin_counts[0])))LikeLike
Frits 8:38 pm on 5 July 2026 Permalink |
A two-stage rocket. More efficient than doing only one standard decompose. S =2 seems to be the optimum.
from collections import defaultdict denoms = [1, 2, 5, 10, 20, 50, 100, 200] N = len(denoms) # remaining target starting with 1 coin of each T = 500 - sum(denoms) # determine smallest <S> denominations last (S > 0) S = 2 # decompose: choose numbers from <ns> so that sum(chosen numbers) equals <t> # and increment these numbers with 1 def decompose(t, ns, m, s=[]): if m == 0: n, r = divmod(t, ns[0]) if not r: yield [n + 1] + s[::-1] else: for i in range(t // ns[m] + 1): yield from decompose(t - i * ns[m], ns, m - 1, s + [i + 1]) # decompose: choose numbers from <ns> so that sum(chosen numbers) <= t def decompose_upto(t, ns, m, s=[]): if m < 0: yield s[::-1] else: for i in range(t // ns[m] + 1): yield from decompose_upto(t - i * ns[m], ns, m - 1, s + [i + 1]) # dictionary of total number of coins still to be made d = defaultdict(list) denoms2 = denoms[S:] # all except the <S> smallest denominations sm = sum(denoms2) # get coins for these denominations not exceeding T for p1 in decompose_upto(T, denoms2, N - S - 1): todo = T + sm - sum(x * y for x, y in zip(p1, denoms2)) d[todo] += [p1] # dictionary of total number of coins occurences freqs = defaultdict(list) for k, vs in sorted(d.items()): # we still need to make <k> pennies with the <S> lowest denominations for p2 in decompose(k, denoms[:S], S - 1): for v in vs: if 10 <= (ncoins := sum(coins := p2 + v)) <= 99: # there were more of one coin than any other if coins.count(max(coins)) == 1: freqs[ncoins] += [coins] # if I told you the total two-figure number of coins you would be able to # work out the numbers of each coin present for k, vs in freqs.items(): if len(vs) != 1: continue # denomination that appeared most ans = max([(x, y) for x, y in zip(vs[0], denoms)]) print(f"answer: {ans[1]}p appeared most ({ans[0]} times)")LikeLike
Frits 6:08 pm on 6 July 2026 Permalink |
Another approach that is sometimes more efficient for hard cases (like denominations 1, 4, 5, 7, 14, 15, 19 and 35).
Jim’s program ran for 80 seconds under CPython for this special case. With this program it takes 2 seconds to finish.
denoms = [1, 2, 5, 10, 20, 50, 100, 200] #denoms = [1, 4, 5, 7, 14, 15, 19, 35] N = len(denoms) # remaining target starting with 1 coin of each T = 500 - sum(denoms) # find the factor that occurs the most fs = sorted([([n for n in denoms if n % i == 0], i) for i in range(2, denoms[-2] + 1)], key=lambda x: (-len(x[0]), -x[1])) # denoms with the list with common factor usage at the back denoms = [n for n in sorted(denoms) if n not in fs[0][0]] + fs[0][0] # decompose: choose numbers from <ns> so that sum(chosen numbers) equals <t> # and increment these numbers with 1 def decompose(t, k, ns, m, s=[]): if m == 0: # we need <k> coins of lowest denomination to make <t> if k * ns[0] == t: coins = [k + 1] + s # there were more of one coin than any other if coins.count(max(coins)) == 1: yield coins else: for i in range(min(k, t // ns[m]) + 1): yield from decompose(t - i * ns[m], k - i, ns, m - 1, [i + 1] + s) # process 2-digit number of coins for k in range(10, 100): sol = [] # make amount <T> with <k - 8> coins cnt = 0 for p in decompose(T, k - len(denoms), denoms, len(denoms) - 1): cnt += 1 if cnt >= 2: break # no unique solution for <k> coins sol = p else: # no break if cnt == 1: times = max(sol) print(f"answer: {denoms[sol.index(times)]}p appeared most ({times} times)") print(f" {sol} * {denoms}")LikeLike
Jim Randell 3:07 pm on 7 July 2026 Permalink |
Considering the possible numbers of coins is a neat idea.
In fact I already have an [[
express_pairs()]] function in enigma.py that supports expressing an amount using a specific number of coins. (I added this to support [[multiset.express()]] some time ago; see Enigma 824).And if we find a second arrangement for a particular number of coins we can move directly onto the next number of coins without examining any other arrangements.
The following Python program runs in 80ms. (Internal runtime is 10ms, so it is slightly faster than my original program).
from enigma import (irange, inf, express_pairs, multiset, unzip, singleton, printf) # denominations (in increasing order) ds = [1, 2, 5, 10, 20, 50, 100, 200] # target total T = 500 # one of each coin is used, so we just need to find the remaining total t = T - sum(ds) # denominations we can use to make <t> vs = list((d, inf) for d in ds if not (d > t)) # express total <t> using exactly <k> coins from <ds> def express(k): for ss in express_pairs(t, vs, inf, k): # check there is a single denomination with maximum quantity (_, qs) = unzip(ss) if qs.count(max(qs)) == 1: yield ss # look for a 2-digit number of coins with a unique arrangement n = len(ds) for k in irange(10, 99): # we need to find a set of (k - n) coins to make the value t ps = singleton(express(k - n)) if ps is None: continue # construct the collection of coins m = multiset.from_pairs(ps).update_from_seq(ds) # output solution printf("{k} coins [{m} -> {t}]", m=m.map2str(), t=m.sum()) for (d, q) in m.most_common(1): printf("-> most common = {q} * {d}p") printf()For your alternate set of denominations (
[1, 4, 5, 7, 14, 15, 19, 35]) it runs in 1.0s (using PyPy 7.3.23), and finds two possible sets:But they give the same answer of 12× 35p coins.
[Note: With the early rejection suggested by Frits below, and some other refinements, the internal runtime of this program is reduced to 1.3ms (and 2.8ms for the alternate set of denominations)].
LikeLike
Frits 10:08 am on 9 July 2026 Permalink |
@Jim, one more improvement.
The case with ds = [4, 5, 6, 7, 13, 16, 33, 116] still runs for 12 seconds.
The run time can be improved by replacing line 25 with:
LikeLike
Frits 10:09 pm on 9 July 2026 Permalink |
Probably my final post for this teaser.
Calculating the number of coins for the 2 lowest denominations in one go.
denoms = [1, 2, 5, 10, 20, 50, 100, 200] N = len(denoms) # remaining target starting with 1 coin of each T = 500 - sum(denoms) # decompose: choose numbers from <ns> so that sum(chosen numbers) equals <t> # and increment these numbers with 1 def decompose(t, k, ns, m, s=[]): if m == 1: # we can calculate the number of coins for the 2 lowest denominations k2, r = divmod(t - k * ns[0], ns[1] - ns[0]) if not (r == 0 and 0 <= k2 <= k): return coins = [k - k2 + 1, k2 + 1] + s # there were more of one coin than any other if coins.count(max(coins)) == 1: yield coins else: if k * ns[m] < t: return # target cannot be achieved in k coins for i in range(0, t // ns[m] + 1): yield from decompose(t - i * ns[m], k - i, ns, m - 1, [i + 1] + s) # process 2-digit number of coins for k in range(10, min(99, N + T // denoms[0]) + 1): sol = [] # make amount <T> with <k - N> coins for p in decompose(T, k - N, denoms, N - 1): if sol and p != sol: break # no unique solution for <k> coins sol = p else: # no break if sol: times = max(sol) print(f"answer: {denoms[sol.index(times)]}p appeared most ({times} times)") print(f" {sol} * {denoms}")LikeLike
Frits 8:01 pm on 7 July 2026 Permalink |
Not restructuring “denoms” and using “if k * ns[m] < t : return" before line 27 gives run times below 20ms.
LikeLike
Frits 8:52 pm on 7 July 2026 Permalink |
@Jim, _express_pairs also seems to benefit hugely by a similar addition (eg “if k * x < t: return" at approx. line 7567 in enigma.py).
LikeLike
Jim Randell 6:55 am on 8 July 2026 Permalink |
@Frits: Good call. This is early rejection for arrangements which cannot possible achieve the required target using the remaining k coins.
I have added it into [[
express_pairs()]] (enigma.py version 2026-07-08).LikeLike
Frits 5:40 pm on 7 July 2026 Permalink |
For the alternate set of denominations ([1, 4, 5, 7, 14, 15, 19, 35]) this program runs in 15ms under CPython 3.14.3. On my Windows computer Jim’s express_pairs() program runs in 3 seconds (using PyPy 7.3.20).
from collections import defaultdict denoms = [1, 2, 5, 10, 20, 50, 100, 200] N = len(denoms) # remaining target starting with 1 coin of each T = 500 - sum(denoms) # find the factor that occurs the most fs = sorted([([n for n in denoms if n % i == 0], i) for i in range(2, denoms[-2] + 1)], key=lambda x: (-len(x[0]), -x[1])) # denoms with the list with common factor usage at the back denoms = [n for n in sorted(denoms) if n not in fs[0][0]] + fs[0][0] d = defaultdict(list) # build dictionary of totals for one, two and three coins for i1, c1 in enumerate(denoms): d[c1] += [(i1, )] for i2, c2 in enumerate(denoms[i1:]): d[c1 + c2] += [(i1, i1 + i2)] for i3, c3 in enumerate(denoms[i1 + i2:]): d[c1 + c2 + c3] += [(i1, i1 + i2, i1 + i2 + i3)] # decompose: choose numbers from <ns> so that sum(chosen numbers) equals <t> # and increment these numbers with 1 def decompose(t, k, ns, m, s=[]): # we still need to use 3 or less coins if m == 0 or k <= 3: if k <= 3: if t in d: for cs in d[t]: # are there <k> coins that add up to <t> if len(cs) == k: coins = [1] * (m + 1) + s for c in cs: coins[c] += 1 # there were more of one coin than any other if coins.count(max(coins)) == 1: yield coins else: # we need <k> coins of lowest denomination to make <t> if k * ns[0] == t: coins = [k + 1] + s # there were more of one coin than any other if coins.count(max(coins)) == 1: yield coins else: # m = 1 --> t - i * ns[1] must be equal to (k - i) * ns[0] # i = (t - k * ns[0]) / (ns[1] - ns[0]) if m > 1: mn = 0 # stop if k * ns[m] < t mx = -1 if k * ns[m] < t else t // ns[m] else: mn, r = divmod(t - k * ns[0], ns[1] - ns[0]) if not (r == 0 and 0 <= mn <= k): return mx = mn for i in range(mn, mx + 1): yield from decompose(t - i * ns[m], k - i, ns, m - 1, [i + 1] + s) # process 2-digit number of coins for k in range(10, 100): sol = [] # make amount <T> with <k - 8> coins for p in decompose(T, k - N, denoms, N - 1): if sol and p != sol: break # no unique solution for <k> coins sol = p else: # no break if sol: times = max(sol) print(f"answer: {denoms[sol.index(times)]}p appeared most ({times} times)") print(f" {sol} * {denoms}")LikeLike
Alex.T.Sutherland 12:15 pm on 8 July 2026 Permalink |
Subject regarding the alternate set of denominations.I have found
many possible singular sets two of which (20 & 21) have already been
found and mentioned.
The following is a sample of my findings of the items and their number :-
Sum = 20
1 1 1 1 1 2 1 12 –> number of items ordered in increasing value.
Sum = 21
2 1 1 1 2 1 1 12
Sum = 30
1 1 1 1 3 7 14 2
Sum = 45
5 5 5 5 4 14 6 1
Sum = 47
5 5 5 5 14 11 1 1
Not sure how it helps solving the original puzzle for a unique answer.
My answer to the puzzle (T3328) comes from a group of 4 sets each with the same sum.
Time :- ~25ms
LikeLike
Jim Randell 3:26 pm on 8 July 2026 Permalink |
@Alex:
Using the alternate set of denominations (
[1, 4, 5, 7, 14, 15, 19, 35]) I found many viable arrangements for 30, 45 and 47 coins. (In fact, 1941 for 30 coins, 103905 for 45 coins, 133002 for 47 coins). But there is only a single viable arrangement for each of 20 and 21 coins.For example, as well as the arrangements you give there are also the following:
LikeLike