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!

Source: codewars | Difficulty: EASY
Tags: Data structures

Mathematics

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

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