Given an array of integers, find the minimum number of steps to make each value equal

Question

I was practicing algorithms and came across this question. I was not able to solve it. I read the editorial provided but it doesn't explain the concept or idea behind the solution.here's the question link(Question).

Problem Statement-->

N boys are sitting in a circle. Each of them have some apples in their hand. You find that the total number of the apples can be divided by N. So you want to divide the apples equally among all the boys. But they are so lazy that each one of them only wants to give one apple to one of the neighbors at one step. Calculate the minimal number of steps to make each boy have the same number of apples.

Input--> First line of input is an integer N and second line contains N numbers, indicating the number of apples of the ith boy.

Output --> Minimal number of steps to make each boy have the same number of apples.

Here's the official implementation:

#include<bits/stdc++.h>
#define mod 10001
using namespace std;
typedef long long LL;
int main()
{
    int n,a[10000],avg;
    LL b[mod],val=0,s=0,m;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    avg=s/n;
    b[0]=0;
    for(int i = 0; i < n-1; i++){
        b[i+1] = b[i]+a[i]-avg;
    }
    sort(b,b+n);
    m = -b[n/2];
    for(int i=0;i<n;i++)
    {
        val += abs(b[i]+m);
    }
    cout<<val;
    return 0;
}

I am looking for an explanation for the above code/logic.How is it giving minimal number of steps? Any alternate solution/ approach (not code necessarily) is welcomed but please explain your approach.

If anything is not clear, then please visit the link or ask in comments section.

Answer 1

Here's my explanation why the algorithm is correct:

The array b tells us how many apples should the i:th boy pass to the right in order for him to have the average amount of apples (which is the goal). If the value is negative, it means he needs to pass the apples to the left. The array b takes into account the apples passed by the previous boys. You can think of it like this: If the first boy has more than the average amount of apples in the beginning b[1] is telling us how many apples is this first boy supposed to pass to the right. If however, he has less than the average in the beginning, b[1] is telling us how many apples is the second boy supposed to pass to the left. In this case the value would be negative. Although the index 1 is now pointing to a different person, it doesnt really matter since we are only interested in the total amount of apples to be passed. After this all the other values b[i] follow in a forced way as long as we suppose that the boys arent passing the apples back and forth without any reason.

Here comes the thing: Above we have seen that if every person passes b[i] amount of apples, we will end up with everybody having the average amount. Now, what if every person passed b[i] + x apples instead, where x is an arbitrary number? We would also end up with every person having the average amount! Why? Because in that case a given person would be passing x more apples to the right, but on the other hand he would get from the person left to him x more apples, so in the end he would have just as many apples as when every person i passed b[i] apples. If every person i passes b[i] apples, the total amount of passed apples would be abs(b[0]) + abs(b[1]) + … + abs(b[n-1]). We know however, that we can get to the goal also by letting the boys pass b[i] + x apples each for any x. Our goal is to minimize the total amoung of passed apples. In other words, our goal is to minimize the value of the expression abs(b[0] - x) + abs(b[1] - x) + … + abs(b[n-1] - x). So we have to find a value x such that this sum is minimal. It turns out that the median of the numbers b[i] is always the optimal solution. Why is that? Now consider choosing a number greater than the median. In that case we could make the sum smaller by making x a bit smaller, since there are more numbers to the left of the current number than to the right of it, since we are on the right side of the median. That follows from the definition of median. The situation is symmetrical if we choose x smaller than the median. So the median itself will always be the optimal solution. If the amount of numbers is even and we have two medians, both of them will be equally optimal and also any number between them.

One thing to notice: The value we assign to b[0] in the beginning doesnt matter at all! You can change that line in the code to b[0] = 2356235; or whatever you like and you will see that the program works just as fine. All the other values will be determined based on this value. You can think of it like this. It doesnt actually matter how many apples the first person passes to the right, as long as all the others act accordingly. By choosing b[0] = 0 we simply find one way of dividing the apples equally. This way of passing the apples isnt however necessarily the optimal. Thats why we use the median trick to find the optimal one.

I hope this helps.

Answer 2

Here is a commented version of the code that should help, but basically, the idea is that since each step, only one apple can move one space, the number of steps needed is the number of apples that need to move + the number of steps each apple needs to move. This is an example of why good comments/var names are important, especially when using a convoluted algorithm like this.

#include<bits/stdc++.h>
#define mod 10001
using namespace std;
typedef long long LL;
int main()
{
    int n,apples[10000],avg;
    LL b[mod],val=0,sum=0,median;

    // Read number of boys
    cin>>n;

    for(int i=0;i<n;i++)
    {
        // Read i'th boy's # of apples
        cin>>apples[i];
        // And add to sum while while we are at it.
        sum+=apples[i];
    }

    // Get average (desired apples per boy)
    avg=sum/n;
    // Clear value of first index
    b[0]=0;
    // Assuming only passing right, 
    // How many apples does boy[i] need to pass right? 
    // (Negative value means needs to pass left.)
    for(int i = 0; i < n-1; i++){
        // Apples this boy needs + needs to pass along
        b[i+1] = b[i]+apples[i]-avg;
    }

    // Sort passes
    sort(b,b+n);
    // Take median, save as negative number
    median = -b[n/2];
    // Sum deference of all passes from the median. 
    // (negate steps where both boys needs are met by same pass)
    for(int i=0;i<n;i++)
    {
        val += abs(b[i]+median);
    }

    cout<<val;
    return 0;
}

That is what the code is doing, but someone else is going to need to add the proof of correctness in another answer.