HackerEarth Chocolate distribution problem solution

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.

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