Divide Apples

N boys are sitting in a circle. Each of them have some apples in their hand. You find that the total number of 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.

Example:

Input:  n = 4, a = [1,3,9,7]
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

long long int divideApples(long long int n, long long int a[])
{
    long long int sum = 0;
    for (int i = 0; i < n; i++)
    {

        sum += a[i];
    }
    sum = sum / n;
    long long int b[n] = {0};
    b[0] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        b[i + 1] = b[i] + (a[i] - sum);
    }
    sort(b, b + n);

    long long int median = -b[n / 2];

    long long int val = 0;
    for (int i = 0; i < n; i++)
    {
        val += abs(b[i] + median);
    }
    return val;
}
int main()
{

    long long int n = 4;

    long long int a[n] = {1, 3, 9, 7};

    cout << divideApples(n, a) << "\n";

    return 0;
}