In this HackerEarth Divide Apples problem solution 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.


HackerEarth Divide Apples problem solution


HackerEarth Divide Apples problem solution.

#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;
}