In this HackerEarth Chocolate distribution problem solution There are N people standing in a row with some counti (1 <=i <= N) a number of chocolates in their hands. You have to select a range of people and take all their chocolates with the condition that you should be able to distribute those chocolates equally among M boxes.

Write a program to determine the maximum number of chocolates that can be placed in a box.


HackerEarth Chocolate distribution problem solution


HackerEarth Chocolate distribution problem solution.

#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
long long int last_modulo[MAX];
int main()
{
int testcase ;
scanf("%d" , &testcase);
int arr[MAX];
long long int ans = 0;
while(testcase--)
{
ans = 0;
int n , m ;
scanf("%d %d" , &n , &m);
memset( last_modulo , -1 , sizeof(last_modulo) );
last_modulo[0] = 0;
for( int i = 0 ; i < n ; i++ )
scanf("%d" , &arr[i] );

long long int sum = 0;
for( int i = 0 ; i < n ; i++ )
{
sum += arr[i];
int tmp = sum % m ;
if( last_modulo[ tmp ] == -1 )
{
last_modulo[tmp] = sum ;
}
else
{
ans = max( ans , sum - last_modulo[tmp] );
}
}
printf("%d\n",ans / m );
}
return 0;
}


Second solution

#include <bits/stdc++.h>

using namespace std;

#define bug() printf("BUG\n")
#define bug1(n) printf("bg1 %d\n",n)
#define bug2(a,b) printf("bg2 %d %d\n",a,b)
#define MOD 1000000007
#define ll long long
#define vi vector< int >
#define vll vector< long long >
#define vvi vector< vector< int > >
#define vvll vector< vector< long long > >
#define pi pair< int, int >
#define pll pair< long long, long long >
#define vpi vector< pair< int, int > >
#define vpll vector< pair< long long, long long > >
#define pb(n) push_back(n)
#define mp(a,b) make_pair(a,b)
#define printA(a,n) for(int i = 0;i < n;++i) cout<<a[i]<<" "; cout<<endl;

int main()
{
int t;
scanf("%d",&t);
assert(t >= 1 && t <= 1000);
ll ns = 0;
while(t--)
{
ll n,m;
scanf("%lld %lld",&n,&m);
ns += n;
assert(n >= 1 && n <= 100000);
assert(m >= 1 && m <= 100000);
ll a[n+1],sum = 0;
ll mods[n+1],sums[n+1];
ll firsts[100005]={0},lasts[100005]={0};
a[0] = 0;
mods[0] = 0;
sums[0] = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%lld",&a[i]);
assert(a[i] >= 0 && a[i] <= 100000);
sum += a[i];
sums[i] = sum;
mods[i] = sum%m;
if (mods[i] == 0)
{
lasts[0] = i;
}
else if(firsts[mods[i]] == 0)
{
firsts[mods[i]] = i;
lasts[mods[i]] = i;
}
else
{
lasts[mods[i]] = i;
}
}
if(sum < m)
{
printf("0\n");
continue;
}
if(sum%m == 0)
{
printf("%lld\n", sum/m);
continue;
}
ll ans = 0,temp;
for (int i = 0; i < m; ++i)
{
temp = (sums[lasts[i]] - sums[firsts[i]])/m;
if (temp > ans)
{
ans = temp;
}
}
printf("%lld\n", ans);
}
assert(ns <= 10000000);
return 0;
}