I need to go to the bank and withdraw some money. I need to withdraw $30, $22 to pay my roommate for the internet and $8 for laundry. Since neither of these can make change, I need my $30 to be split into two partitions of the two sizes. That means when the teller asks me how I want my $30 I am going to have to make a request. I could tell them I want it in a twenty, a fiver, and five ones. But I want to make my request as simple as possible as to avoid having to repeat myself. To make my request simpler I could ask that my cash contain a twenty and at least 2 ones because the 8 is implied by the total, but better yet I could simply request that one of the bills I receive be a one dollar bill (If you are not convinced of this just try to make 29 dollars without making 8).

So that's all fine and dandy but I need to do this calculation every time I go to the bank so I thought I would write a program to do this (have you write a program to do this for me).

Your program or function should take a list of integers representing all the payments I need to make and a set of integers representing the denominations of bills available at the bank, and you must output the smallest list of denominations such that every way to make the total that includes that list of denominations can be cleanly divided into the list of payments.

Extra rules

  • You may assume that the denomination list will always contain a 1 or you may add it to each list yourself.

  • Some inputs will have multiple minimal solutions. In these cases you may output either one.

This is so answers will be scored in bytes with less bytes being better.

Test Cases

Payments, denominations    -> requests
{22,8}    {1,2,5,10,20,50} -> {1} or {2}
{2,1,2}   {1,5}            -> {1}
{20,10}   {1,2,5,10,20,50} -> {}
{1,1,1,1} {1,2}            -> {1,1,1}
{20,6}    {1,4,5}          -> {1}
{2,6}     {1,2,7}          -> {2}
{22, 11}  {1, 3, 30, 50}   -> {1, 3}
{44, 22}  {1, 3, 30, 50}   -> {1, 3, 3, 30}
  • 24
    \$\begingroup\$ At first I thought this was spam or off-topic or something... \$\endgroup\$ Sep 21, 2017 at 16:57
  • 1
    \$\begingroup\$ @EriktheOutgolfer paragraphs hurt challenges so much >_< \$\endgroup\$ Sep 21, 2017 at 17:46
  • \$\begingroup\$ I don't understand why {1} isn't the output for all the examples? My understanding is that when you go up to the teller, and say (e.g.) "I'd like $8, one partition of $2 and another of $6. Also, there must be at least one $1 bill", why that wouldn't produce a partition e.g. of ($1,$1) and ($2,$2,$2)? Why doesn't $1 work, and why do you have to specify $2? \$\endgroup\$ Feb 23, 2021 at 22:36
  • 2
    \$\begingroup\$ @ChartZBelatedly I had to read the task several times but I think now I understand it. You try to give the teller as little information as necessary. To stay with the example with the 2$ and 6$ partition. If you give the teller the information you need 8$ and want one of them to be a 1$ bill there are different outcomes: (1,7), (1,1,2,2,2), (1,1,1,1,1,1,1,1) etc. The last two would do the job, but (1,7) would not fit our partition. Although it did meet the criteria. It has at least one 1$ bill and added up we get 8$. \$\endgroup\$ Mar 18, 2021 at 9:11

2 Answers 2


JavaScript (ES6), 485 476 bytes

Alright ... this is a monster. :-(
But it's a rather fast monster that solves all test cases almost instantly.

I may attempt some more advanced golfing later, but I've already spent far too much time on it.


Test cases


console.log(JSON.stringify(f([22,8], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([2,1,2], [1,5])))
console.log(JSON.stringify(f([20,10], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([1,1,1,1], [1,2])))
console.log(JSON.stringify(f([20,6], [1,4,5])))
console.log(JSON.stringify(f([2,6], [1,2,7])))
console.log(JSON.stringify(f([22,11], [1,3,30,50])))
console.log(JSON.stringify(f([44,22], [1,3,30,50])))


NB: This is not matching the current version anymore, but is much easier to read that way.

// b = list of payments, a = list of bills,
// L = list from which the requested bills are chosen
f = (b, a, L = [...a]) => (
  // U = helper function that computes the sum of an array
  U = a => ~~eval(a.join`+`),

  // P = function that computes the summed Cartesian products of arrays of integers
  // e.g. P([[[1,2],[3,4]], [[10,20],[30,40]]]) --> [[33,44], [13,24], [31,42], [11,22]]
  P = (e, C = [], R = []) => e[0].map(v => R =
    (c = v.map((x, i) => x + (C[i] | 0)), e[1]) ? [...P(e.slice(1), c), ...R] : [c, ...R]
  ) && R,

  // G = function that takes a target amount and a list of requested bills and returns
  // all combinations that contain the requested bills and add up to this amount;
  // each combination is translated into a list of number of bills such as [2,0,0,1,0]
  G = (n, l) => (
    S = [],
    g = (n, l) => n ?
      a.map(x => x < l[0] | x > n || g(n - x, [x, ...l])) :
      S = [l.map(v => s[a.indexOf(v)]++, s = [...a].fill(0)) && s, ...S]
  )(n, l) && S,

  // compute X = list of possible bill combinations to process all payments
  X = P(b.map(a => G(a, []))),

  // compute the powerset of L and sort it from shortest to longest list
  L.reduce((a, x) => [...a, ...a.map(y => [x, ...y])], [[]])
  .sort((a, b) => a[b.length] || -1)

  .find(L => (
    // compute Y = list of possible combinations to reach the total amount,
    // using the requested bills
    Y = G(U(b) - U(L), L.sort((a, b) => a - b)),

    // exit if Y is not empty and all combinations in Y allow to generate all payments
    Y[0] && !Y.some(a => X.every(b => b + '' != a)))

  // if no solution was found, enlarge the set of requested bills and try again
  || f(b, a, [...a, ...L])
  • \$\begingroup\$ I'm not too familiar with javascript, but can you reduce the && to & and the || to |? \$\endgroup\$ Sep 22, 2017 at 20:11
  • \$\begingroup\$ @TaylorScott This is only possible under certain conditions. For instance, a || b will evaluate b only if a is falsy, while a | b will unconditionally perform a bitwise OR between a and b. \$\endgroup\$
    – Arnauld
    Sep 22, 2017 at 20:18

Python 2, 456 455 bytes

Extremely, extremely, extremely slow!!!! Should work correctly on all the input examples given enough time

Edit: Saved 1 byte thanks to @Jonathan Frech

def F(p,d):v=sum(p);E=enumerate;l=lambda x,y:y[1:]and(x>=y[-1]and[k+[y[-1]]for k in l(x-y[-1],y)]+l(x,y[:-1])or l(x,y[:-1]))or[[1]*x];Q=l(v,d);m=lambda x,y=[0]*len(p):x and max(m(x[1:],[a+x[0]*(i==j)for i,a in E(y)])for j,_ in E(y))or y==p;f=lambda x,h=[]:x and min([S for i,s in E(x)for S in h+[s],f(x[:i]+x[i+1:],h+[s])if all(map(m,filter(lambda k:all(k.count(j)>=S.count(j)for j in S),Q)))],key=len)or[1]*v;print-(all(map(m,Q))-1)*min(map(f,Q),key=len)

Try it online!


p,d=input() # Read input
v=sum(p) # Save a byte by keeping track of the total money withdrawn
E=enumerate # We use enumerate a lot
# Generates the possible combinations of denominators that add up to the withdrawn amount 
l=lambda x,y:y[1:]and(x>=y[-1]and[k+[y[-1]]for k in l(x-y[-1],y)]+l(x,y[:-1])or l(x,y[:-1]))or[[1]*x]
# We use the list generated by l quite a few times
# Checks if we can divide a list of denominators x in such a way that we get the wished division of the money
m=lambda x,y=[0]*len(p):x and max(m(x[1:],[a+x[0]*(i==j)for i,a in E(y)])for j,_ in E(y))or y==p
# For a list of denominators, it tries all possible combinations of the denominators as input to the teller, selecting the one with minimum length
f=lambda x,h=[]:x and min([S for i,s in E(x)for S in h+[s],f(x[:i]+x[i+1:],h+[s])if all(map(m,filter(lambda k:all(k.count(j)>=S.count(j)for j in S),Q)))],key=len)or[1]*v
# Call f with all possible lists of denominators, and check if saying nothing to the teller will work

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.