# Background

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.

# Input

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

# Output

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

# Rules

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

• FrobeniusNumber in Mathematica. – alephalpha Sep 6 '15 at 16:30
• 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. – orlp Sep 6 '15 at 16:58
• Are there any limits of run time or memory usage? – Dennis Sep 6 '15 at 17:01
• On Stack Overflow there was a code golf question like this a while back – Downgoat Sep 6 '15 at 17:39
• 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. – isaacg Sep 7 '15 at 11:52

# Pyth, 23 bytes

ef!fqTs.b*NYQY^UTlQS*FQ


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

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ


## Explanation

                   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


# Perl, 6054 51 bytes

50 bytes code + 1 bytes command line

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/  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


For an arbitrary entry of coprimes, $$\a_1, a_2,\ldots$/extract_tex], Frobenius' amount is given by a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])  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=scan();max((1:(min(a)*(b<-max(a))))[-colSums(combn(outer(a,0:b),sum(!!a)))])  A slightly shorter version (72 bytes) that most often takes too log or too much space to run on Try it online is a=scan();max((1:(b<-prod(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])  # Python2, 188 187 bytes def g(L): M=max(L);i=r=0;s=*M;l=+s[1:] 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 else:r=i s[i]+=1;i=(i+1)%M  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, 120130126128127 125 chars f=a=>{r=[1|a.sort((a,b)=>a-b)]}.repeat(a*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)  Alternative 126 chars version: f=a=>{r=;a.sort((a,b)=>a-b);for(q=0;q<a*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join.lastIndexOf(0)}  Test: "[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
})

• You can replace the forEach( with map( – Ypnypn Sep 7 '15 at 2:45

# Ruby, 108 bytes

->a{b=;m=a.min
(1..1.0/0).map{|n|c=p
a.map{|x|c|=(b!=b-[n-x])}
c&& b<<=n
return n-m if b[-m]&&b[-m]>n-m}}


Try it online!

# Explanation

->a{                                         input list
b=;                                      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
`