The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not possible to pay certain amounts, like 4 foos, using these coins. Nevertheless, all large enough amounts can be formed. Your job is to find the largest amount that can't be formed with the coins (5 foos in this case), which is known as the coin problem.


Your input is a list L = [n1, n2, ..., nk] of positive integers, representing the values of coins in circulation. Two things are guaranteed about it:

  • The GCD of the elements of L is 1.
  • L does not contain the number 1.

It may be unsorted and/or contain duplicates (think special edition coins).


Since the GCD of L is 1, every large enough integer m can be expressed as a non-negative linear combination of its elements; in other words, we have

 m = a1*n1 + a2*n2 + ... + ak*nk 

for some integers ai ≥ 0. Your output is the largest integer that cannot be expressed in this form. As a hint, it is known that the output is always less than (n1 - 1)*(nk - 1), if n1 and nk are the maximal and minimal elements of L (reference).


You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. If your language has a built-in operation for this, you may not use it. There are no requirements for time or memory efficiency, except that you should be able to evaluate the test cases before posting your answer.

After I posted this challenge, user @vihan pointed out that Stack Overflow has an exact duplicate. Based on this Meta discussion, this challenge will not be deleted as a duplicate; however, I ask that all answers based on those of the SO version should cite the originals, be given the Community Wiki status, and be deleted if the original author wishes to post their answer here.

Test Cases

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49
  • 6
    \$\begingroup\$ FrobeniusNumber in Mathematica. \$\endgroup\$
    – alephalpha
    Sep 6, 2015 at 16:30
  • 3
    \$\begingroup\$ There is a way better upper bound, found in this paper that establishes (p - 1)(q - 1) as the upper bound, where p and q are the smallest and biggest element of the set. \$\endgroup\$
    – orlp
    Sep 6, 2015 at 16:58
  • 2
    \$\begingroup\$ Are there any limits of run time or memory usage? \$\endgroup\$
    – Dennis
    Sep 6, 2015 at 17:01
  • 1
    \$\begingroup\$ On Stack Overflow there was a code golf question like this a while back \$\endgroup\$
    – Downgoat
    Sep 6, 2015 at 17:39
  • 1
    \$\begingroup\$ I have a 13 byte Pyth solution that can do [2,3] in a reasonable amount of time and nothing else. [2,5] would create about a million Python lists in memory. \$\endgroup\$
    – isaacg
    Sep 7, 2015 at 11:52

6 Answers 6


Perl, 60 54 51 bytes

50 bytes code + 1 bytes command line


The basic approach is to let the regex engine do the hard work with string matching. For example, it will construct a regex similar to ^(.{3})*(.{7})*(.{8})*$ and match against a string of length n where n descends from the product of the inputs until it fails to match.

Note that this will become exponentially slow as the number of arguments increases.

Usage: Arguments are read in from STDIN (new line separated), for example:

printf "101\n10" | perl -p entry.pl

Pyth, 23 bytes


It's very slow, as it checks all values up to the product of all the coins. Here's a version that is almost identical, but 1) reduces the set of coins to those not divisible by each other and 2) only checks values up to (max(coins) - 1) * (min(coins) - 1) (47 bytes):



                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

R, 84 78 72 bytes

For an arbitrary entry of coprimes, \$a_1, a_2,\ldots\$, Frobenius' amount is given by


Try it online!

since it is always smaller than the product of the extreme \$a_i\$'s. It is then a matter of combining all possible combinations (and more) within that range. Thanks to Cole Beck for suggesting outer with no "*" and colSums rather than `apply(...,2,sum)'.

A faster but longer (by two bytes) version only considers max(a):


A slightly shorter version (72 bytes) that most often takes too log or too much space to run on Try it online is


Python2, 188 187 bytes

def g(L):
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1

The second indentation is rendered as 4 spaces on SO, those should be tabs.

Actually a 'fast' solution, not bruteforce, uses 'Wilf's Method' as described here.


Javascript ES6, 120 130 126 128 127 125 chars


Alternative 126 chars version:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}


"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
  • 1
    \$\begingroup\$ You can replace the forEach( with map( \$\endgroup\$
    – Ypnypn
    Sep 7, 2015 at 2:45

Ruby, 108 bytes

c&& b<<=n
return n-m if b[-m]&&b[-m]>n-m}}

Try it online!


->a{                                         input list
    b=[0];                                      list of representable integers
        m=a.min                                     minimum input
    (1..1.0/0).map{|n|                       n in range 1..
        c=p                                    c = false
          a.map{|x|c|=(b!=b-[n-x])}              check if n goes in b
            c&& b<<=n                                   put n in b
              return n-m if b[-m]&&b[-m]>n-m}}            return if m values in a row

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.