fastest way to distribute a quantity to elements of an array such that the difference of pairs is minimal?

Question

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

e.g. arr = [4,2,0] and x = 10;

the answer should be [6,5,5];

it is obligatory to use all of x.

Answer 1

Assuming the position of unchanged values does not need to be preserved:

0. convert into a min heap ("heapify", O(n))
1. repeat pop&count minimal values from the heap until
   - empty: distribute rest: done -or-
   - top is greater:
   • If there's not enough left to make all minimums equal top, distribute rest: done
   • else decrease rest and continue 1.

O(n+#increased_values*log(n))
Final write back of increased values left as an exercise (for now).

Answer 2

Here's a solution that can beat both my binary search answer, as well as don't talk just code's answer at some larger input lengths. The idea is to sort the array and find the largest minimum by accumulation, traversing from smaller to larger, with O(1) space for the latter, avoiding pop operations.

Test link.

Python code:

def g(A, x):
  s = sorted(range(len(A)), key=lambda i: A[i])

  total = x
  count = 1
  curr = A[s[0]]
  to_add = 0
  extra = 0

  for i in range(1, len(A)):
    diff = A[s[i]] - curr
    needed = count * diff
    if needed >= total:
      break
    curr = A[s[i]]
    total -= needed
    count += 1

  if total:
    extra, to_add = divmod(total, count)
  
  for i in range(count):
    A[s[i]] = curr + extra
    if to_add:
      A[s[i]] += 1
      to_add -= 1
  
  return A

Answer 3

For large inputs with smaller range, it can be more efficient to binary search the target minimum. I didn't expect it, but apparently this solution can be up to seven times faster than don't talk just code's answer even for medium size ranges. Here's an example with range 20 (seven times faster), and one with 100,000,000 (two times faster): https://ideone.com/X6GxFD. As we increase input length, this answer seems to be significantly faster even for the full 64 bit range.

Python code:

def f(A, x):
  smallest = min(A)
 
  lo = smallest
  hi = smallest + x
 
  while lo < hi:
    mid = lo + (hi - lo) // 2
 
    can_reach = True
    temp = x
 
    for a in A:
      if a <= mid:
        diff = mid - a
        if diff > temp:
          can_reach = False
          break
        else:
          temp -= diff
 
    if can_reach:
      lo = mid + 1
    else:
      hi = mid
 
  target = lo - 1
 
  for i, a in enumerate(A):
    if a < target:
      x -= target - a
      A[i] = target
 
  if x:
    for i, a in enumerate(A):
      if a == target:
        A[i] += 1
        x -= 1
        if x == 0:
          break
 
  return A

Answer 4

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')

Answer 5

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.