On fictional islands of Matunga archipelage several different tribes use fictional currency - tung. One tung is a very small amount, so all payments are made with coins of different values. For example, one tribe use coins of 7 and 9 tungs, another - 6, 10 and 11 tungs. Every tribe has at least 2 different coins.
Also every tribe has a shop with remarkable feature: if you find an item N tungs worth, you always can find an item priced N+1 tungs in the same shop.
Your goal is to write the function min_price(coins) which finds out the minimum price of item which can be in sale in Matunga tribe shop, knowing the values of coins used there.

Function should return -1 if result is not accessible (i.e. coins of these values can't cover natural row from N to infinity without gaps).

For example, some tribe has coins of 3 and 5 tungs. They can't sell items of 4 or 7 tungs, because 4 and 7 can't be represented as a sum of 3's and 5's. But starting from 8 tungs you can do it with every sum: 8 is 5+3, 9 is 3+3+3, 10 is 5+5, 11 is 5+3+3 and so on. So the answer for this set of coins is 8.

Difficulty: interview

Starter code:

def gcd(a, *r):
	

Solutions:
from fractions import gcd

def min_price(nums):
    nums.sort()
    ns = [0] + [float('inf')] * (nums[0] - 1)
    for c in nums[1:]:
        d = gcd(nums[0], c)
        for r in range(d):
            n = min(ns[r::d], default=float('inf'))
            if n < float('inf'):
                for j in range(nums[0] // d):
                    n += c
                    p = n % nums[0]
                    ns[p] = n = min(n, ns[p])
    max_ = max(ns) or 1
    return max_ - nums[0] + 1 if max_ < float('inf') else -1

from math import gcd as builtin_gcd
 
"""
This problem could be seen as finding the Frobenius number
Algorithm used
https://brg.a2hosted.com/?page_id=563
based on
The Money Changing Problem Revisited: Computing the Frobenius Number in Time O(ka1), by Sebastian Bocker and Zsuzsanna Liptak, June 2004, Technical Report number 2004-2, University of Bielefeld, Technical Faculty.

"""    
    
def gcd(a, *r):
  for b in r:
    a = builtin_gcd(a, b)
  return a
 
def lcm(a, *r):
  for b in r:
    a *= b // builtin_gcd(a, b)
  return abs(a)
 
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
 
  
  if len(a) < 2 or gcd(*a) > 1:
    return -1
  return max(__residue_table(sorted(a))) - min(a)

def min_price(a):
    if 1 in a:
        return 1
    else :
        fn = frobenius_number(a) 
        return fn + 1 if not fn == -1 else fn

import math
def min_price(coins):
    if coins == []:
        return -1
    if do_gcd(coins) !=1:
        return -1
    if min(coins) == 1:
        return 1
    if len(coins) == 2:
        return do_lcm(coins) - sum(coins) + 1
    a = sorted(coins)
    a1 = a[0]
    k = len(a)
    inf = math.inf
    n = [0]
    for i in range(1, a1):
        n.append(inf)
    for i in range(1, k):
        d = math.gcd(a1, a[i])
        for r in range(d):
            nn = inf
            for q in range(r, a1, d):
                if (q % d) == r:
                    nn = min(nn, n[q])
            if nn < inf:
                for j in range(int(a1/d) - 1):
                    nn = nn + a[i]
                    p = nn % a1
                    nn = min(nn, n[p])
                    n[p] = nn
    return max(n) - a1 + 1

def do_gcd(array):
    if len(array) == 1:
        return array[0]
    if len(array) == 2:
        return math.gcd(array[0], array[1])
    return math.gcd(array[0], do_gcd(array[1:]))

def do_lcm(array):
    return int(array[0]*array[1]/math.gcd(array[0], array[1]))

def gcd(a, b):
    while a:
        b, a = a, b % a
    return b

def min_price(coins):
    if(1 in coins): return 1
    coins.sort()
    print(coins)
    n = [0] + [-1] * (coins[0] - 1)
    for i in range(1, len(coins)):
        d = gcd(coins[0], coins[i])
        for r in range(d):
            try:
                nn = min(n[q] for q in range(r, coins[0], d) if n[q] != -1)
            except:
                continue
            if nn != -1:
                for c in range(coins[0] // d):
                    nn += coins[i]
                    p = nn % coins[0]
                    nn = min(nn, n[p]) if n[p] != -1 else nn
                    n[p] = nn
    
    if(len(coins) < 2 or -1 in n): return -1
    return max(n) - coins[0] + 1

from math import gcd as builtin_gcd
 
def gcd(a, *r):
  for b in r:
    a = builtin_gcd(a, b)
  return a
 
def lcm(a, *r):
  for b in r:
    a *= b // builtin_gcd(a, b)
  return abs(a)
 
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
 
  if len(a) < 2 or gcd(*a) > 1:
    return -1
  return max(max(__residue_table(sorted(a))) - min(a) +1,1)

def min_price(coins):
    return frobenius_number(coins)

# Breadth first decreasing (BFD) algorithm for the Frobenius
# number following Beihoffer, Hendry, Nijenhuis, and Wagon
# ("Faster Algorithms For Frobenius Numbers", The Electronic
# Journal of Combinatorics, 2005).

from functools import reduce
from collections import deque

def gcd(a,b):
    while b != 0: a, b = b, a % b
    return a

def min_price(a):
    if 1 in a: return 1
    elif reduce(gcd, a) != 1: return -1

    n = len(a)
    a.sort()
    a1 = a[0]

    q = deque([0])
    h = set([0])
    
    p = [n] + [0] * a1
    s = [0] + [a1 * a[-1]] * (a1 - 1)
    amod = [x % a1 for x in a]

    while q:
        v = q.popleft()
        h.remove(v)
        
        for j in range(1, p[v]):
            u = v + amod[j]
            if u >= a1: u -= a1

            w = s[v] + a[j]
            
            # This performance-enhancing
            # condition is given on p. 10.
            if w == s[u] and j < p[u] - 1:
                p[u] = j + 1
            
            if w < s[u]:
                s[u] = w
                p[u] = j + 1
                if u not in h:
                    q.append(u)
                    h.add(u)

    return max(s) - a1 + 1

# All credit to PuzzlingInPython's blog post on the Bocker Liptak algorithm for calculating the Frobenius number.

from math import gcd as builtin_gcd
 
def gcd(a, *r):
  for b in r:
    a = builtin_gcd(a, b)
  return a
 
def lcm(a, *r):
  for b in r:
    a *= b // builtin_gcd(a, b)
  return abs(a)
 
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
 
  if len(a) < 2 or gcd(*a) > 1:
    return -1
  return max(max(__residue_table(sorted(a))) - min(a) +1,1)

def min_price(coins):
    return frobenius_number(coins)

#BFDU algorithm from:
#Faster Algorithms for Frobenius Numbers
#the electronic journal of combinatorics 12(2005), #R27

#TODO: Implement DQQD(U) from the same paper

import heapq
import collections
from math import gcd

def frobenius(a):
    
    n = len(a)
    if n == 2:
        return a[0]*a[1]-a[0]-a[1]
    
    a.sort()
    a1, an = a[0], a[-1]
    s = [an] * a1; s[0]=0
    p = [0]*a1; p[0]=n-1
    q = [[] for _ in range(a1)]; q[0].append(0)
    z = [0]
    amod = [-99] + [x % a1 for x in a]
    aquot = [-99] + [x // a1 for x in a]
    a = [-99] + a
    
    q = collections.deque([0])
    qs = {0}
    p=[0]*a1; p[0]=n
    s= [a1*an]*a1; s[0]=0
     
    while q:
        v = q.popleft()
        qs.remove(v)
        for j in range(2, p[v]+1):
            u = v + amod[j]
            if u >= a1: u = u - a1
            w = s[v]+a[j]
            if w < s[u]:
                s[u] = w
                p[u]=j
                if u not in qs:
                    q.append(u)
                    qs.add(u)
            elif w == s[u] and j < p[u]:
                p[u] = j
    return max(s) - a1

    
def min_price(a):
    
    if 1 in a: return 1
    if not a: return -1
    
    cd = a[0]
    for z in a:
        cd = gcd(cd, z)
    if cd != 1:
        return -1    
        
    return frobenius(a) + 1

from math import gcd
from functools import reduce

# https://brg.a2hosted.com/?page_id=563
# The Money Changing Problem Revisited: 
# Computing the Frobenius Numberin Time O(ka1) by Bocker and Liptak
# http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.389.4933&rep=rep1&type=pdf
def frobenius_number(a):
  def __residue_table(a):
    n = [0] + [None] * (a[0] - 1)
    for i in range(1, len(a)):
      d = gcd(a[0], a[i])
      for r in range(d):
        try:
          nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None)
        except ValueError:
          continue
        if nn is not None:
          for c in range(a[0] // d):
            nn += a[i]
            p = nn % a[0]
            nn = min(nn, n[p]) if n[p] is not None else nn
            n[p] = nn
    return n
  if len(a) < 2 or reduce(gcd, a) > 1:
    return -1
  return max(__residue_table(sorted(a))) - min(a)

def min_price(coins):
  if min(coins) == 1:
      return 1
  f = frobenius_number(coins)
  return f + 1 if f >= 0 else -1

from math import gcd
def min_price(coins):
    if 1 in coins:
        return 1

# Round Robin Algorithm [from https://pdfs.semanticscholar.org/14ac/14a15ebc31b58a4ac04328f9824f743a1e4e.pdf]
    coins = sorted(coins)
    myinf = 4000000000
    n = [0] + [myinf] * (coins[0] - 1)
    for i in range(1, len(coins)):
        d = gcd(coins[0], coins[i])
        for r in range(0, d):
            nn = min([n[q] for q in range(r, r + coins[0] - d + 1, d)])
            if nn != myinf:
                for j in range(0, coins[0] // d):
                    nn = nn + coins[i]
                    p = nn % coins[0]
                    nn = min(nn, n[p])
                    n[p] = nn

    maxn = max(n)
    if maxn == myinf:
        return -1

    return max(n) - coins[0] + 1