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 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.