CODEWITHSUNDEEP
algorithm
Lingxi
Lingxi

Reputation: 14967

Distribution strategy to minimize the maximum value in an array

Recently, I come across this problem in solving another problem. I have a solution myself. But I'm not quite satisfied with its time complexity. So, I'm turning to you guys for a possible better solution. The problem is as follows:

Suppose there is an integer array int arr[N]. I have an integer value val in my hand to distribute to arr. For example, I can increase arr[0] by val, or arr[2] by 1 and arr[3] by val - 1, and so on. The goal is to minimize the maximum value in arr after the distribution. There may be multiple solutions, and anyone will just do.

My current solution is as follows. It's trivial and takes O(val) time. I have a feeling that a better solution exists.

for (int i = 0; i < val; ++i) {
  // increase the minimum value in arr by 1
}

Upvotes: 2

Views: 1259

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Here's a linear-time algorithm. First try to increase everything to the current max. If we have to keep going, distribute the rest as evenly as possible. In untested Python:

def distribute(arr, val):
    maxarr = max(arr)
    for x in arr:
        val -= min(maxarr - x, val)
    return maxarr - (-val) // len(arr)

The double minus silliness is to get ceiling division.

Upvotes: 4

Related Questions