Sunday Times Teaser 3328 – Loose Change

by BRG on 5 July 2026

by Andrew Skidmore

Published Sunday July 05 2026 (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?

From → Uncategorized

6 Comments Leave one →

BRG permalink


# the coin denominations
den = (200, 100, 50, 20, 10, 5, 2, 1)

# split integer <tps> into sums of multiples of the 
# values in <ps> with all values present
def split(tps, ps, rs=[]):
  if len(ps) == 1:
    if tps and tps % ps[0] == 0:
      yield rs + [tps // ps[0]]
  else:
    for p in range(1, tps // ps[0] + 1):
      yield from split(tps - p * ps[0], ps[1:], rs + [p])

# collect coins making £5 indexed on the number of coins used
nc2s = {}
for ns in split(500, den):
  # there is one coin used more than all others
  if ns.count(max(ns)) == 1:
    # the number of coins used has two digits
    if 10 <= (sm := sum(ns)) < 100:
      nc2s[sm] = nc2s.get(sm, []) + [ns]

# look for a number of coins that is unique
for k, v in nc2s.items():
  vs, *_ = v
  if not _:
    f = ' + '.join(f'{v}x{d}p' for v, d in zip(vs, den))
    print(f"{max(vs) + 1} x {den[vs.index(max(vs))]}p coins [{f.replace('1x', '')}]")

# the coin denominations

den = (200, 100, 50, 20, 10, 5, 2, 1)

# split integer <tps> into sums of multiples of the

# values in <ps> with all values present

def split(tps, ps, rs=[]):

if len(ps) == 1:

if tps and tps % ps[0] == 0:

yield rs + [tps // ps[0]]

else:

for p in range(1, tps // ps[0] + 1):

yield from split(tps - p * ps[0], ps[1:], rs + [p])

# collect coins making £5 indexed on the number of coins used

nc2s = {}

for ns in split(500, den):

# there is one coin used more than all others

if ns.count(max(ns)) == 1:

# the number of coins used has two digits

if 10 <= (sm := sum(ns)) < 100:

nc2s[sm] = nc2s.get(sm, []) + [ns]

# look for a number of coins that is unique

for k, v in nc2s.items():

vs, *_ = v

if not _:

f = ' + '.join(f'{v}x{d}p' for v, d in zip(vs, den))

print(f"{max(vs) + 1} x {den[vs.index(max(vs))]}p coins [{f.replace('1x', '')}]")

John Z. permalink


# coin values - 8 in all (this number is used below)
coins = (1, 2, 5, 10, 20, 50, 100, 200) 

# split <amount> into coins (lifted from Brian's solution to 3321)
def split(amount, pck=0, seq=()):
  if pck == len(coins):
    if amount  == 0:
      yield seq
  else:
    for np in range(amount // coins[pck] + 1):
      if (rem := amount - np * coins[pck]) >= 0:
          yield from split(rem, pck + 1, seq + (np,))

# as each coin is used at least once we can start with what remains
ramount = 500 - sum(coins)        

# dictionary indexed on total coins; values: tuple of number of each coin
change = {}
for s in split(ramount):
  # two figure number of coins; more of one coin than any other
  if 9 < (tcoins := sum(s) + 8) < 100 and s.count(max(s)) == 1:
    change[tcoins] = change.get(tcoins, []) + [s]

for n, cs in change.items():
  # there must only be one way of reaching this number of coins
  if len(cs) == 1:
    # get most used coin and number of uses - 1
    muc = coins[cs[0].index(nou := max(cs[0]))]
    print(f'Most used coin: {muc}p; used {nou + 1} times')
    print(*[f'{coins[i]}p: {n + 1}  ' for i, n in enumerate(cs[0])])

# coin values - 8 in all (this number is used below)

coins = (1, 2, 5, 10, 20, 50, 100, 200)

# split <amount> into coins (lifted from Brian's solution to 3321)

def split(amount, pck=0, seq=()):

if pck == len(coins):

if amount == 0:

yield seq

else:

for np in range(amount // coins[pck] + 1):

if (rem := amount - np * coins[pck]) >= 0:

yield from split(rem, pck + 1, seq + (np,))

# as each coin is used at least once we can start with what remains

ramount = 500 - sum(coins)

# dictionary indexed on total coins; values: tuple of number of each coin

change = {}

for s in split(ramount):

# two figure number of coins; more of one coin than any other

if 9 < (tcoins := sum(s) + 8) < 100 and s.count(max(s)) == 1:

change[tcoins] = change.get(tcoins, []) + [s]

for n, cs in change.items():

# there must only be one way of reaching this number of coins

if len(cs) == 1:

# get most used coin and number of uses - 1

muc = coins[cs[0].index(nou := max(cs[0]))]

print(f'Most used coin: {muc}p; used {nou + 1} times')

print(*[f'{coins[i]}p: {n + 1} ' for i, n in enumerate(cs[0])])

John Z. permalink

I was mystified as to why Brian’s code which is very similar to mine, runs much faster. It turns out that having the coins/den tuple with coins in increasing order of value in my code as opposed to decreasing order in Brian’s code results in 4.5 times as many calls to the recursive function.

Reply
- BRG permalink
  
  Hi John,
  
  Yes, I found this out quite early on after originally using the increasing order.
  
  But Frits also sent me a further speed up that he had found. When we are down to the last denomination, we don’t need to loop to find the number of coins needed since if the remainder is zero we add [0] to the output; if not we add [remainder // last denomination] provided this division is exact.
  
  These two speed ups make a big difference to the speed. I also realised that your line 12 is not needed.
  
  Reply
  - John Z. permalink
    
    Frits’ speed up takes the number of calls of from 181603 down to 7772, a better than 23 to 1 ratio.
    
    Reply

Frits permalink

This is my fastest code so far (published on th S2T2 site). It can handle alternate denominations like [1, 4, 5, 7, 14, 15, 19, 35] and [4, 6, 8, 10, 12, 14, 34, 43] relatively well. It runs faster under PyPy.


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
    k1, r = divmod(t - k * ns[0], ns[1] - ns[0])
    if not (r == 0 and 0 <= k1 <= k): return
    coins = [k - k1 + 1, k1 + 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}")

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

k1, r = divmod(t - k * ns[0], ns[1] - ns[0])

if not (r == 0 and 0 <= k1 <= k): return

coins = [k - k1 + 1, k1 + 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}")

Sunday Times Teaser 3328 – Loose Change

by Andrew Skidmore

Published Sunday July 05 2026 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta