Impossible-to-find bug in a program that equalizes wealth in a group (UVA 10137, "The Trip")

Question

I wrote a solution for this competitive programming problem. It passed all the test cases, except it was off by one for the last case, and I can't figure out why. The problem can be stated like this: given how many pennies each person in a group has, how much money has to change hands so that everyone in the group will be within one penny of each other in wealth?

My program is simple. I modified it to just operate on an array of how many pennies everyone has:

def transfer(A):
    A.sort(key = lambda x:-x)
    extra = sum(A) % len(A)
    average = sum(A) // len(A)

    high = sum([abs(x - (average+1)) for x in A[:extra]])
    low = sum([abs(x - average) for x in A[extra:]])

    return (high+low)/2

The test case that it fails on is the following:

print(transfer([613, 944, 7845, 8908, 12312, 22378, 27877, 54757, 55476, 90707, 91289, 178189]))

My code says the answer is 240710, while the "correct" answer is 240709. Where is my bug?

Answer 1

The consensus seems to be that the reason I got a different answer is that I use exclusively integer arithmetic, and their answer uses float arithmetic. While their algorithm would be correct in infinite precision, it turns out that in this case, by a weird fluke, float imprecision gives an off-by-one. This is verified by gcc compiling code that gives a different answer than mine, but clang compiling code that gives the same answer I found.