Story:
In the realm of numbers, the apocalypse has arrived. Hordes of zombie numbers have infiltrated and are ready to turn everything into undead. The properties of zombies are truly apocalyptic: they reproduce themselves unlimitedly and freely interact with each other. Anyone who equals them is doomed. Out of an infinite number of natural numbers, only a few remain. This world needs a hero who leads remaining numbers in hope for survival: The highest number to lead those who still remain.

Briefing:
There is a list of positive natural numbers. Find the largest number that cannot be represented as the sum of this numbers, given that each number can be added unlimited times. Return this number, either 0 if there are no such numbers, or -1 if there are an infinite number of them.

Example:
```
Let's say [3,4] are given numbers. Lets check each number one by one:
1 - (no solution) - good
2 - (no solution) - good
3 = 3 won't go
4 = 4 won't go
5 - (no solution) - good
6 = 3+3 won't go
7 = 3+4 won't go
8 = 4+4 won't go
9 = 3+3+3 won't go
10 = 3+3+4 won't go
11 = 3+4+4 won't go
13 = 3+3+3+4 won't go
```
...and so on. So 5 is the biggest 'good'. return 5

Test specs:
Random cases will input up to 10 numbers with up to 1000 value

Special thanks:
Thanks to Voile-sama, mathsisfun-sama, and Avanta-sama for heavy assistance. And to everyone who tried and beaten the kata ^_^

Difficulty: interview

Starter code:

def survivor(zombies):
	

Solutions:
from functools import reduce
from math import gcd

def survivor(a):
    """Round Robin by Bocker & Liptak"""
    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
                for _ in range(a[0] // d):
                    nn += a[i]
                    p = nn % a[0]
                    if n[p] is not None: nn = min(nn, n[p])
                    n[p] = nn
        return n

    a.sort()
    if len(a) < 1 or reduce(gcd, a) > 1: return -1
    if a[0] == 1: return 0
    return max(__residue_table(a)) - a[0]

# a1, a2, a3, ... are the zombies numbers
# For a number x to be represented as a sum of those zombies, it means n-a1 or n-a2 or n-a3 or ... has to be represented
# From that, we can dynamically find if a number is representable (function "represent")
# 
# an is the biggest zombie number
# If x is represented, then x + an is represented too
# Wich means we can divide numbers from 0 into groups of size an
# If the element i of a group is representable, then it will still be in the next group
# 
# If the kth group is the same as the (k-1)th group, then it means no new number is representable
# In this case, there will be an infinite number of survivors
# 
# If all number in the kth are representable, then it means the biggest non-representable number was in the previous group
# So we just find the biggest non-representable number of the previous group
# 
# After an iterations of this, either we found there are infinites survivors
# Or we already filled the group (since they have a size of an)

from functools import lru_cache

def survivor(zombies):
    if not zombies: return -1
    nums = sorted(zombies)
    represent = lru_cache(maxsize=None)(lambda x: not x or any(represent(x-y) for y in nums[::-1] if x >= y))
    maxi = nums[-1]
    current = [0]*maxi
    for x in range(0, maxi**2, maxi):
        temp = [current[i] or represent(x+i) for i in range(maxi)]
        if temp == current: return -1
        if all(temp):
            y = next(i for i,v in enumerate(current[::-1]) if not v)
            return max(0, x-y-1)
        current = temp

def gcd(a,b): #Just a simple Euclidean algorithm to compute gcd
    while (b != 0):
      a,b = b,a%b
    return a



def survivor(zombies):

    if (len(zombies) == 0): #First let's deal with lists of length == 0
        return -1

    zombies.sort()    #Then let's sort the list
    if zombies[0] == 1:    #If zombie[0] is 1, we know every number will be biten
        return 0  
    
    ####################################################################
    #Let's check if there is an infinity of solutions.                 #
    #It is equivalent to see if gcd of all numbers is different from 1.#
    ####################################################################
    
    zombies_gcd = 0
    for z in zombies:
        zombies_gcd = gcd(z,zombies_gcd)
    if zombies_gcd != 1:
        return -1
    
    ####################################################################
    #Now let's list every number to see who's the last one to be bitten#
    ####################################################################
    
    length = zombies[-1] + 1
    who_is_bitten = [False for i in range(length)]
    

    for z in zombies:    #Of courses zombies are considered as bitten
        who_is_bitten[z] = True        
    
    i = zombies[0] - 1    #We know that zombies[0]-1 is a survivor so we can begin by that number
    
    #We keep track of the number of consecutive zombies
    consecutive_zombies = 0
    

    while (consecutive_zombies < zombies[0]): #we know if there are zombies[0] consecutive zombies in a row, 
                                              #then there won't be any survivor after that
        if not(who_is_bitten[i]):         #If the number is not bitten, then it becomes the new last survivor
            result = i
            consecutive_zombies = 0
        else:         #Otherwise, it bites other numbers which are at range
            consecutive_zombies += 1
            while (i + zombies[-1] >= len(who_is_bitten)): #if the list is too short we have to add new numbers
                who_is_bitten.append(False)
    
            for z in zombies:
                who_is_bitten[i + z] = True  #Then number i bites numbers that are at its range
        
        i += 1
        
    return result

from fractions import gcd
from functools import reduce
from itertools import count

def survivor(l):
    if 1 in l: return 0
    if len(l) < 2 or reduce(gcd,l) > 1: return -1
    if len(l) == 2: return (l[0]-1)*(l[1]-1)-1
    m,t,r,w=[True],0,0,max(l)
    for i in count(1):
        m = m[-w:] + [any(m[-n] for n in l if len(m)>=n)]
        if not m[-1]: t,r = i,0
        else: r += 1
        if r == w: break
    return t

import bisect
from operator import itemgetter
from itertools import groupby

def survivor(zombies):
    if(1 in zombies):
        return 0
    gcdl = False
    for i in zombies:
        if(gcdl==True):
            break
        for x in zombies:
            if(i!=x and gcd(i,x)==1):
                gcdl = True
                break
    if(gcdl == False):
        return -1
    if(len(zombies)==2):
        return zombies[0]*zombies[1]-zombies[0]-zombies[1]
    
    zombies.sort()
    c = zombies.copy()
    e = [1]
    l = max(c)
    N = len(c)
    y=0
    F = zombies[0]*zombies[1]+zombies[0]
    
    for i in range(1,F):
        #print(e)
        x = 0
        for j in range(0,N):
            if(i>=c[j]):
                x+=e[i-c[j]]
        e.append(x)
        e[i] = x
        if(x==0):
            y=i
        
    return y

def gcd(a,b):
    # if a and b are both zero, print an error and return 0
    if a == 0 and b == 0:
        #print("WARNING: gcd called with both arguments equal to zero.",
        #file=sys.stderr)
        return 0
    # make sure a and b are both nonnegative
    if a < 0: a = -a
    if b < 0: b = -b
    while b != 0:
        new_a = b
        new_b = a % b
        a = new_a
        b = new_b
    return a

import math
def survivor(zombies):
    size = len(zombies)
    if size == 0:
        return -1
    if (1 in zombies):
        return 0

    gcd = zombies[0]
    for i in range(len(zombies) - 1):
        gcd = math.gcd(gcd, zombies[1 + i])
    if gcd != 1:
        return -1

    maxSize = (zombies[0] * zombies[1]) - zombies[0] - zombies[1]
    posible = [False for _ in range(maxSize + 1)]
    posible[0] = True


    for zombie in zombies:
        if zombie <= maxSize:
            for i in range(zombie, maxSize + 1):
                if not posible[i]:
                    posible[i] = posible[i - zombie]
    largest = 0
    for i in range(maxSize + 1):
        if not posible[i]:
            largest = i
    return largest

import math
from heapq import *
from itertools import combinations

def closure_gen(s):
    keys,seen=set(s),set(s)
    q=sorted(seen)
    while q:
        curr=heappop(q)
        for next in filter(lambda v:not v in seen, [curr+i for i in keys]):
            heappush(q,next)
            seen.add(next)
        yield curr
def gcd(s):
    if len(s)==0:return -1
    if len(s)==1:return s[0]
    res,*s=s
    while s:
        n,*s=s
        res=math.gcd(res,n)
    return res        
    
def survivor(zombies):
    zombies=sorted(set(zombies))
    if not zombies: return -1
    if 1 in zombies: return 0
    if gcd(zombies)>1: return -1
    g=closure_gen(zombies)
    curr=loop=big=0
    zmin=min(zombies)
    while loop<zmin:
        prev,curr=curr,next(g)
        if prev+1==curr:
            loop+=1
        else:
            print(loop,curr)
            loop=0
            big=curr-1
    return big        

from math import gcd
from functools import reduce
import heapq

def gcd2(xs): return reduce(gcd, xs, xs[0])

def gen(xs):
    seen = set()
    q = list(sorted(xs))
    while True:
        curr = heapq.heappop(q)
        yield curr
        for x in xs:
            t = curr + x
            if t not in seen:
                heapq.heappush(q, t)
                seen.add(t)


def survivor(xs):
    if 1 in xs: return 0
    if not xs or gcd2(xs) > 1: return -1
    i, cnt, m = 0, 1, min(xs)
    g = gen(xs)
    for x in g:
        if x != i + cnt: cnt, i = 1, x
        else: cnt += 1
        if cnt >= m: break
    return i - 1



import math
import functools

def survivor(zombies):
    zombies.sort()
    if not zombies: return -1
    divisor = functools.reduce(math.gcd, zombies)
    if divisor > 1:
        return -1
    
    A = zombies
    Q = [0]
    P = [len(zombies)] + ([None] * (A[0] - 1))
    S = [0]
    a = [A[0] * A[len(A) - 1]] * (A[0] - 1)
    S = S + a
    Amod = list(map(lambda x : x % A[0], A))
    while len(Q) > 0 :
        v = Q[0]
        Q.pop(0)
        for j in range(2, P[v] + 1):
            u = v + Amod[j - 1]
            if u >= A[0]:
                u = u - A[0]
            w = S[v] + A[j - 1]
            if w < S[u]:
                S[u] = w
                P[u] = j
                if u not in Q:
                    Q.append(u)
    if (int(max(S)) - A[0]) < 0 :
        return 0
    return int(max(S)) - A[0]

import math
def survivor(zombies):
    if zombies == []:
        return -1
    if do_gcd(zombies) !=1:
        return -1
    if min(zombies) == 1:
        return 0
    if len(zombies) == 2:
        return do_lcm(zombies) - sum(zombies)
    a = sorted(zombies)
    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(a1):
                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

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