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.
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：
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
CodePudding user response：
Assuming that you are to minimize the maximum difference between any pair of numbers, then this is the general approach:
- Sort the numbers
- Find the lowest number(s)
- 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,
- If X is used up then exit.
- If not then got to step #2 and repeat.
Obviously, you can improve step #3 with a little bit of math.
CodePudding user response：
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.
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
CodePudding user response：
Assuming the position of unchanged values does not need to be preserved:
- convert into a min heap ("heapify", O(n))
- 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).