在列表中均匀分布(Google Foobar:Maximum Equality)

Question

这个问题来自谷歌Foobar,我的代码传递了除最后一次测试以外的所有测试,其中隐藏了输入/输出.

提示

换句话说,选择数组的两个元素x [i]和x [j](i与j不同)并同时将x [i]递增1并将x [j]递减1.您的目标是得到数组中的许多元素都具有相同的值.

例如,如果数组是[1,4,1],您可以执行如下操作:

从第一辆车发送一只兔子到第0辆:增加x [0],递减x [1],得到[2,3,1]从第一辆车发送一只兔子到第二辆:增加x [2],减少x [1],得到[2,2,2].

现在阵列中的所有元素都是相同的,并且您有一个向Beta Rabbit报告的策略!

请注意,如果数组是[1,2],我们可以得到的最大可能相等元素数是1,因为汽车中的兔子数量永远不会相同.

编写一个函数answer(x),它取整数x的数组,并根据需要多次执行上述命令,返回我们可以获得的相等数组元素的最大数量.

列车中的汽车数量(x中的元素)至少为2,不超过100.想要共享汽车的兔子数量(x的每个元素)将是[0的范围内的整数],百万].

我的代码

from collections import Counter

def most_common(lst):
    data = Counter(lst)
    return data.most_common(1)[0][1]

def answer(x):
    """The goal is to take all of the rabbits in list x and distribute
    them equally across the original list elements."""
    total = sum(x)
    length = len(x)
    # Find out how many are left over when distributing niavely.
    div, mod = divmod(total, length)
    # Because of the variable size of the list, the remainder
    # might be greater than the length of the list.
    # I just realized this is unnecessary.
    while mod > length:
        div += length
        mod -= length
    # Create a new list the size of x with the base number of rabbits.
    result = [div] * length
    # Distribute the leftovers from earlier across the list.
    for i in xrange(mod):
        result[i] += 1
    # Return the most common element.
    return most_common(result)

它在我自己的测试目的下运行良好,在十秒左右的时间内处理一百万次尝试.但它在未知输入下失败了.

我错过了一些明显的东西,还是我做了一个我不应该做的假设？

Answer 1

抱歉,您的代码在我的测试中无效.我喂它[0,0,0,0,22]然后回到[5,5,4,4,4]的列表,回答为3; 最大值是4辆相同的汽车,原始输入就是一个这样的例子.[4,4,4,4,6]将是另一个.我怀疑这是你的问题,而且数据库中还有其他一些这样的例子.

对于N辆汽车,最大值是N(如果兔子数量可以被汽车数量整除)或N-1.这看起来很简单,我担心我错过了问题的限制.它没有要求平衡的人口,正如尽可能多的汽车人口应该是平等的.简而言之:

def answer(census):
    size = len(census)
    return size if sum(census) % size == 0 else (size-1)