We have the integer `9457`. 

We distribute its digits in two buckets having the following possible distributions (we put the generated numbers as strings and we add the corresponding formed integers for each partition):
```
- one bucket with one digit and the other with three digits 
[['9'], ['4','5','7']] --> ['9','457'] --> 9 + 457 = 466
[['9','5','7'], ['4']] --> ['957','4'] --> 957 + 4 = 961
[['9','4','7'], ['5']] --> ['947','5'] --> 947 + 5 = 952
[['9','4','5'], ['7']] --> ['945','7'] --> 945 + 7 = 952

- two buckets with 2 digits each:
[['9','4'], ['5','7']] --> ['94','57'] --> 94 + 57 = 151
[['9','5'], ['4','7']] --> ['95','47'] --> 95 + 47 = 142
[['9','7'], ['4','5']] --> ['97','45'] --> 97 + 45 = 142
```

Now we distribute the digits of that integer in three buckets, and we do the same presentation as above:
```
one bucket of two digits and two buckets with one digit each:
[['9'], ['4'], ['5','7']] --> ['9','4','57'] --> 9 + 4 + 57 = 70
[['9','4'], ['5'], ['7']] --> ['94','5','7'] --> 94 + 5 + 7 = 106
[['9'], ['4', '5'], ['7']] --> ['9','45','7'] --> 9 + 45 + 7 = 61
[['9'], ['5'], ['4','7']] --> ['9','5','47'] --> 9 + 5 + 47 = 61
[['9','5'], ['4'], ['7']] --> ['95','4','7'] --> 95 + 4 + 7 = 106
[['9','7'], ['4'], ['5']] --> ['97','4','5'] --> 97 + 4 + 5 = 106
```
Finally we distribute the digits in the maximum possible amount of buckets for this integer, four buckets, with an unique distribution:
```
One digit in each bucket.
[['9'], ['4'], ['5'], ['7']] --> ['9','4','5','7'] --> 9 + 4 + 5 + 7 = 25
```
In the distribution we can observe the following aspects:

- the order of the buckets does not matter

- the order of the digits in each bucket matters; the available digits have the same order than in the original number.

- the amount of buckets varies from two up to the amount of digits

The function, `f =` `bucket_digit_distributions_total_sum`, gives for each integer, the result of the big sum of the total addition of generated numbers for each distribution of digits.
```python
bucket_digit_distributions_total_sum(9457) === 4301 # 466 + 961 + 952 + 952 + 151 + 142 + 142 + 70 + 106 + 61 + 61 + 106 + 106 + 25 = 4301
```
It is interesting to see the value of this function for a number that has one or more zeroes as digits, for example:
```python
bucket_digit_distributions_total_sum(10001) === 5466
```
Given an integer `n`, with its corresponding value of the above function, `f(n)`, and another integer `z`, find the closest and higher integer to n, `nf`, such `f(nf) > f(n) + z`.

Example:
```python
find(10001,100) === 10003
find(30000, 1000) === 30046
``` 
Features of the random tests:
```
100 <= n <= 1500000
50 <= z <= 6000
```

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Combinatorics

Mathematics

Matrices

Data structures

Starter code: def find(n,z):
	

Solutions:
def subsets(collection):
	if len(collection) == 1:
		yield [collection]
		return
	first = collection[0]
	for smaller in subsets(collection[1:]):
		yield ([first] + smaller)
		for (n, subset) in enumerate(smaller):
			yield (smaller[:n] + [first + subset] + smaller[n + 1:])

def bucket_digit_distributions_total_sum(n):
	return sum((sum(map(int, sub)) for sub in subsets(str(n)))) - n

def find(n, z):
	f_nf = bucket_digit_distributions_total_sum(n) + z
	while 1:
		n += 1
		if bucket_digit_distributions_total_sum(n) > f_nf:
			return n


from functools import reduce
from itertools import count
coefs = [[22, 13, 4], [365, 167, 50, 14], [5415, 2130, 627, 177, 51], [75802, 27067, 7897, 2254, 661, 202], [1025823, 343605, 100002, 28929, 8643, 2694, 876]]

def f(n):
	return sum((c * int(d) for (c, d) in zip(coefs[len(str(n)) - 3], str(n))))

def find(n, z):
	t = f(n) + z
	for nf in count(n):
		if f(nf) > t:
			return nf


from itertools import count

def rec(n):
	if not n:
		yield 0
		return
	for i in range(1 << len(n) - 1):
		tmp = [[], []]
		for t in n:
			(i, r) = divmod(i, 2)
			tmp[r].append(t)
		(x, y) = (int(''.join(tmp[0])), tmp[1])
		for k in rec(y):
			yield (x + k)
val = lambda n: sum(rec(str(n))) - n

def find(n, z):
	z += val(n)
	return next((i for i in count(n + 1) if val(i) > z))


def find(n, z):
	r = n + 1
	sumn = sumof(n)
	while True:
		if sumof(r) > sumn + z:
			return r
		r += 1
	return 'Perhaps this is a different way to solve the kata, but it works ;-)(not cheat)'

def sumof(n):
	fm = [[], [], [], [22, 13, 4], [365, 167, 50, 14], [5415, 2130, 627, 177, 51], [75802, 27067, 7897, 2254, 661, 202], [123456, 123456, 123456, 123456, 123456, 123456, 123456]]
	l = 1 if n < 10 else 2 if n < 100 else 3 if n < 1000 else 4 if n < 10000 else 5 if n < 100000 else 6 if n < 1000000 else 7
	(a, i, r) = (fm[l], l - 1, 0)
	while n > 0:
		t = n % 10
		n //= 10
		r += t * a[i]
		i -= 1
	return r


def partition(collection):
	if len(collection) == 1:
		yield [collection]
		return
	first = collection[0]
	for smaller in partition(collection[1:]):
		for (n, subset) in enumerate(smaller):
			yield (smaller[:n] + [[first] + subset] + smaller[n + 1:])
		yield ([[first]] + smaller)

def part_sum(part_list):
	tot_sum = 0
	for elem in part_list:
		tot_sum += sum((int(''.join(x)) for x in elem))
	return tot_sum

def find(n, z):
	min_sum = part_sum([x for x in partition(list(str(n)))][1:]) + z
	i = 1
	nf_sum = part_sum([x for x in partition(list(str(n + i)))][1:])
	while nf_sum <= min_sum:
		i += 1
		nf_sum = part_sum([x for x in partition(list(str(n + i)))][1:])
	return n + i


def find(n, z):
	lim = bucket_digit_distributions_total_sum(n) + z
	num = n
	while True:
		num += 1
		res = bucket_digit_distributions_total_sum(num)
		if lim < res:
			return num
	return num

def bucket_digit_distributions_total_sum(n):
	parts = get_partitions(list(str(n)), len(str(n)))
	buckets_sum = 0
	for p in parts:
		if len(p) > 1:
			b = [int(''.join(l)) for l in p]
			buckets_sum += sum(b)
	return buckets_sum

def get_partitions(lst, n):
	if n <= 0:
		yield []
		return
	else:
		curr = lst[n - 1]
		for part in get_partitions(lst, n - 1):
			for l in list(part):
				l.append(curr)
				yield part
				l.pop()
			yield (part + [[curr]])


def get_partitionr(ss):
	out = []
	if len(ss) <= 1:
		return [ss]
	for i in range(2 ** len(ss) // 2):
		parts = [[], []]
		for item in ss:
			parts[i & 1].append(item)
			i >>= 1
		bb = get_partitionr(parts[1])
		for b in bb:
			out.append([parts[0]] + b)
	return out

def add(parts):
	total = 0
	for part in parts:
		total += sum((int(''.join(p)) if isinstance(p, list) else int(p) for p in part))
	return total

def find(n, z):
	parts = get_partitionr(list(str(n)))[1:]
	add_parts = add(parts)
	target = add_parts + z
	while add_parts <= target:
		n += 1
		parts = get_partitionr(list(str(n)))[1:]
		add_parts = add(parts)
	return n


import itertools

def find(n, z):
	find.combination_dict = {0: ((),), 1: (((0,),),)}

	def get_combination(length):
		if length not in find.combination_dict:
			for i in range(length):
				get_combination(i)
			template = list(range(length))
			result = [{tuple((i for i in template))}]
			for init_tuple_length in range(1, length):
				for c in itertools.combinations(template, init_tuple_length):
					remain = [i for i in template if i not in c]
					for combinations in find.combination_dict[length - init_tuple_length]:
						new_combination = [tuple(c)]
						for combination in combinations:
							new_combination.append(tuple((remain[index] for index in combination)))
						if set(new_combination) not in result:
							result.append(set(new_combination))
			find.combination_dict[length] = tuple((tuple(i) for i in result))
		return find.combination_dict[length]

	def f(num):
		num = str(num)
		value = []
		for combinations in get_combination(len(num)):
			if len(combinations) != 1:
				for combination in combinations:
					value.append(''.join((num[i] for i in combination)))
		return sum(map(int, value))
	limit = f(n) + z
	for nf in itertools.count(n):
		if f(nf) > limit:
			return nf