CODEWITHSUNDEEP
arrayssortinggreedy
Sujan Dutta
Sujan Dutta

Reputation: 171

Find a way to minimize max difference

N people needs different amount of money given by : X_i (1<=i<=N) But we have a fixed money denoted by M. It may happen that M is less than the total money which is required to fulfill everyone's need.

I want to find a way to distribute the money (M) such that the maximum difference between the required money and given money is minimize over all the people. Is there a way to do that?

  e.g : N = 4, M=3

  X1=5, X2=4, X3=2, X4=2

  In this case we should distribute like : 2 1 0 0 
  so difference array is : 3 3 2 2
  maximum difference is minimized (which is 3)

Any interesting link are also welcome on this topic.

Upvotes: 1

Views: 310

Answers (2)

fafl
fafl

Reputation: 7385

This can be solved in a single pass after ordering the amounts of debt descendingly. Debt is paid from top to bottom. This python code should make it clear:

def get_max_debt_after_distribution(debt, money):

    if not debt:
        raise ValueError('Please specify debt')

    debt.sort(reverse=True)
    debt.append(0)  # Add zero debt to simplify algorithm

    for i in range(1, len(debt)):
        last_amount = debt[i-1]
        new_amount = debt[i]

        # To bring the max diff down from "last_amount" to "new_amount",
        # we need to pay the difference for each debt
        to_pay = (last_amount - new_amount) * i

        # Check if we have enough money to pay the full amount
        if to_pay <= money:
            money -= to_pay
        else:
            # Out of money. Remaining money goes to highest debts.
            return last_amount - int(money / i)

    # There was enough money to pay all the debt
    return 0

print(get_max_debt_after_distribution([5, 4, 2, 2], 3))  # prints 3
print(get_max_debt_after_distribution([5, 5, 5, 5], 7))  # prints 4

Upvotes: 1

Racso
Racso

Reputation: 2449

This can be solved with a greedy approach.

First, notice that the initial desired amounts are also the initial differences between required and given money (because you have given 0 to everybody). Therefore, for your example, the differences start in [5, 4, 2, 2].

Second, notice that giving money to any person other than the one who has the maximum difference at a given time doesn't reduce the maximum difference. For example, if the array is 5, 4, 2, 2, giving money to anyone other than the first person won't reduce the maximum difference: [5, 3, 2, 2], [5, 4, 1, 2], [5, 4, 2, 1] (the maximum difference stays at 5).

Therefore, you should always give one coin to the person that has the maximum difference at a given point (or any of those, if there's a tie), until you run out of coins: [5, 4, 2, 2] -> [4, 4, 2, 2] -> [3, 4, 2, 2] -> [3, 3, 2, 2] -> [2, 3, 2, 2] -> [2, 2, 2, 2], etc.

Of course, when implementing the algorithm, you don't actually need to give the coins one by one, but this is the general idea of what you should do.

Upvotes: 0

Related Questions