In this Kata, you will be given two numbers, n and k and your task will be to return the k-digit array that sums to n and has the maximum possible GCD.

For example, given `n = 12, k = 3`, there are a number of possible `3-digit` arrays that sum to `12`, such as `[1,2,9], [2,3,7], [2,4,6], ...` and so on. Of all the possibilities, the one with the highest GCD is `[2,4,6]`. Therefore, `solve(12,3) = [2,4,6]`.

Note also that digits cannot be repeated within the sub-array, so `[1,1,10]` is not a possibility. Lastly, if there is no such array, return an empty array.

More examples in the test cases.

Good luck!

Difficulty: introductory

Starter code:

def solve(n,k):
	

Solutions:
def solve(n,k):
    maxGcd = 2*n // (k * (k+1))
    for gcd in range(maxGcd, 0, -1):
        last = n-gcd * k*(k-1)//2
        if not last % gcd:
            return [gcd*x if x != k else last for x in range(1,k+1)]
    return []

solve=lambda n,k: [n] if k==1 else (lambda r: r[-1] if len(r) else [])(list(filter(lambda a: a[-1]>0 and a[-1] > a[-2] and not a[-1]%a[0], ([j*i for j in range(1,k)]+[int(n-k*(k-1)/2*i)] for i in range(1,int(n/2)+1)))))

def solve(n,k):
    d=int(2*n/(k*(k+1)))
    for i in range(d,0,-1):
        if n%i==0:
            d=i
            break
    if d==0:
        return []
    r=[d*i for i in range(1,k)]
    r.append(n-sum(r))
    return r

def solve(n, k):
    if n <= 0: return []
    if k == 1: return [n]
    s = k * (k + 1) // 2
    for d in range(n // s, 0, -1):
        if n % d != 0: continue
        return [d * i for i in range(1, k)] + [n - k * (k - 1) // 2 * d]
    return []

def solve(n, k):
    b, r = 2*n // (k*(k+1)), 1
    if not b: return []
    for x in range(1, int(n**0.5)+1):
        if n%x: continue
        if r < x <= b: r = x
        if r < n//x <= b: r = n//x
    return [r*i for i in range(1, k)] + [n - (r*k*(k-1)//2)]

def unorderedPartitions(targetNum, targetSize, minNum = 1):
    if targetSize == 1:
        return [[targetNum]]
    partitions = []
    for partNum in range(minNum, targetNum // targetSize + 1):
        partitions += [[partNum] + part for part in unorderedPartitions(targetNum - partNum, targetSize - 1, partNum + 1)]
        return partitions # return first found partition only

def solve(n, k):
    factors = set()
    for f in range(1, int(n ** 0.5) + 1):
        if n % f == 0:
            factors.add(f)
            factors.add(n // f)
    factors = sorted(factors, reverse = True)
    # minimum sum of (n // gcd)
    minSum = k * (k + 1) // 2
    for factor in factors:
        if factor * minSum > n:
            continue
        partition = unorderedPartitions(n // factor, k)[0]
        if len(partition) == len(set(partition)):
            return [x * factor for x in partition]
    return []

def solve(n,k):
    x = int(n/k)
    if x <= 1:
        return []
    def check(y):
        while y > 0:
            z = [i*y for i in range(1, k+1)]
            if sum(z) == n:
                return z
            elif sum(z) < n:
                break
            elif sum(z) > n:
                pass
            y -= 1
        return z
    y = x
    z = check(y)
    mod = n - sum(z[:-1])
    if mod%z[0] == 0:
        return z[:-1] + [mod]
    while y > 0:
        y -= 1
        z = check(y)
        mod = n - sum(z[:-1])
        if mod%z[0] == 0:
            return z[:-1] + [mod]


def solve(n,k):
    psum = (k * (k+1)) / 2
    if n >= psum:
        min_int = n // psum
        while min_int > 0:
            if n % min_int == 0:
                return populate(n,min_int,k)
            min_int -= 1
    return []

def populate(n,s,k):
    output = []
    m = n
    for i in range(1, k):
        output.append(i*s)
        m -= i*s
    output.append(m)
    return output