given an array of numbers and an integer x, distribute x such that the difference between any pairs is minimum possible.

eg arr = [4,2,0] and x = 10;

ans should be [6,5,5];

it is obligatory to use x.

CodePudding user response：

Compute the final mean as (sum(arr) x) / len(arr). That would be the ideal target for all numbers if we could also decrease.

The rounded down quotient tells us the minimum every number shall become, and the remainder tells us how many numbers shall get an additional 1 added. Do that after eliminating numbers already too large.

Total time O(n log n).

Python implementation:

def distribute(arr, x):
    total = sum(arr)   x
    I = sorted(range(len(arr)), key=arr.__getitem__)
    while I:
        minimum, additional = divmod(total, len(I))
        if arr[I[-1]] <= minimum:
            break
        total -= arr[I.pop()]
    for i in sorted(I):
        arr[i] = minimum
        if additional > 0:
            arr[i]  = 1
            additional -= 1

Results from testing some hardcoded inputs, larger random inputs, and exhaustive small inputs:

433103 tests passed
0 tests failed

Full code (Try it online!):

from random import choices
from itertools import product

def distribute(arr, x):
    total = sum(arr)   x
    I = sorted(range(len(arr)), key=arr.__getitem__)
    while I:
        minimum, additional = divmod(total, len(I))
        if arr[I[-1]] <= minimum:
            break
        total -= arr[I.pop()]
    for i in sorted(I):
        arr[i] = minimum
        if additional > 0:
            arr[i]  = 1
            additional -= 1

def naive(arr, x):
    for _ in range(x):
        arr[arr.index(min(arr))]  = 1

passed = failed = 0

def test(arr, x):
    expect = arr.copy()
    naive(expect, x)
    result = arr.copy()
    distribute(result, x)
    global passed, failed
    if result == expect:
        passed  = 1
    else:
        failed  = 1
        print('failed:')
        print(f'{arr =    }')
        print(f'{expect = }')
        print(f'{result = }')
        print()

# Tests from OP, me, and David
test([4, 2, 0], 10)
test([4, 2, 99, 0], 10)
test([20, 15, 10, 5, 0], 10)

# Random larger tests
for x in range(1000):
    arr = choices(range(100), k=100)
    test(arr, x)

# Exhaustive smaller tests
for n in range(5):
    for arr in product(range(10), repeat=n):
        arr = list(arr)
        for x in range(n * 10):
            test(arr, x)

print(f'{passed} tests passed')
print(f'{failed} tests failed')

CodePudding user response：

Assuming that you are to minimize the maximum difference between any pair of numbers, then this is the general approach:

1. Sort the numbers
2. Find the lowest number(s)
3. If there are Y lowest numbers, then decrement X by Y and add 1 to each of the lowest numbers until either X runs out, or the lowest numbers become equal to the next lowest numbers,
4. If X is used up then exit.
5. If not then got to step #2 and repeat.

Obviously, you can improve step #3 with a little bit of math.