Evenly distribute within a list (Google Foobar: Maximum Equality)

Question

This question comes from Google Foobar, and my code passes all but the last test, with the input/output hidden.

The prompt

In other words, choose two elements of the array, x[i] and x[j] (i distinct from j) and simultaneously increment x[i] by 1 and decrement x[j] by 1. Your goal is to get as many elements of the array to have equal value as you can.

For example, if the array was [1,4,1] you could perform the operations as follows:

Send a rabbit from the 1st car to the 0th: increment x[0], decrement x[1], resulting in [2,3,1] Send a rabbit from the 1st car to the 2nd: increment x[2], decrement x[1], resulting in [2,2,2].

All the elements are of the array are equal now, and you've got a strategy to report back to Beta Rabbit!

Note that if the array was [1,2], the maximum possible number of equal elements we could get is 1, as the cars could never have the same number of rabbits in them.

Write a function answer(x), which takes the array of integers x and returns the maximum number of equal array elements that we can get, by doing the above described command as many times as needed.

The number of cars in the train (elements in x) will be at least 2, and no more than 100. The number of rabbits that want to share a car (each element of x) will be an integer in the range [0, 1000000].

My code

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)

It runs well under my own testing purposes, handling one million tries in ten or so seconds. But it fails under an unknown input.

Have I missed something obvious, or did I make an assumption I shouldn't have?

Answer 1

Sorry, but your code doesn't work in my testing. I fed it [0, 0, 0, 0, 22] and got back a list of [5, 5, 4, 4, 4] for an answer of 3; the maximum would be 4 identical cars, with the original input being one such example. [4, 4, 4, 4, 6] would be another. I suspect that's your problem, and that there are quite a few other such examples in the data base.

For N cars, the maximum would be either N (if the rabbit population is divisible by the number of cars) or N-1. This seems so simple that I fear I'm missing a restriction in the problem. It didn't ask for a balanced population, just as many car populations as possible should be equal. In short:

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