The Coin Problem

Question

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

Answer 1

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

Answer 2

Perl, 60 54 51 bytes

50 bytes code + 1 bytes command line

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Will carry on golfing and post an explanation later. 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

Answer 3

R, 84 78 bytes

For an arbitrary entry of coprimes, \$a_1, a_2,\ldots\$, 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))))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

A slightly shorter version (78 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)))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Answer 4

Python2, 188 187 bytes

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+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.

Answer 5

Javascript ES6, 120 130 126 128 127 125 chars

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*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=[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)}

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

Answer 6

Ruby, 108 bytes

->a{b=[0];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=[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