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.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

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

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 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]
			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


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

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