HackerEarth Mathison and the divisible trios problem solution

YASH PAL, 31 July 202414 February 2026

In this HackerEarth Mathison and the divisible trios problem solution, Mathison has discovered an old piece of paper with N integers written on it. Let’s call this given sequence of numbers A. In his History class, Mathison has learned that a trio of numbers is special if and only if their sum is divisible by a mythical constant M.

Mathison tries to find out how many distinct triplets of numbers, from the piece of paper, have their sum divisible by M. Unfortunately, this problem is quite hard to crack and he needs your help.

HackerEarth Mathison and the divisible trios problem solution

HackerEarth Mathison and the divisible trios problem solution.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  vector<int> A(N);
  for (int &x: A){
    cin >> x;
    x %= M;
  }

  int answer = 0;

  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      for (int k = j + 1; k < N; k++)
        if ((A[i] + A[j] + A[k]) % M == 0)
          answer++;

  cout << answer << endl;

  return 0;
}

Second solution

import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class b
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
    static Random rnd=new Random();
    
    static long c3(long curr)
    {
        return (curr*(curr-1)*(curr-2))/6;
    }
    
    public static void main(String args[]) throws Exception
    {
        int n=sc.nextInt(),m=sc.nextInt();int[] a=new int[n];long[] cnt=new long[m];
        
        if(n<1|| n>200000 || m<1 || m>10000)
        {
            throw new Exception("Wrong");
        }

        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
            
            if(a[i]<0 || a[i]>(int)(2e9))
            {
                throw new Exception("Wrong");
            }
            
            cnt[a[i]%m]++;
        }
        
        long res=0;long[] p=new long[m],x=new long[m];
        
        for(int i=0;i<m;i++)
        {
            int curr=(m-i)%m;long add=(cnt[i]*(cnt[i]-1L))/2;
            
            long mul=(cnt[i]*p[curr]);res=(res+mul);
            
            int curr2=(m-i-i)%m;
            
            if(curr2<0)
            {
                curr2+=m;
            }
            
            mul=(add*x[curr2]);res=(res+mul);
                
            for(int j=0;j<i;j++)
            {
                long now=(cnt[i]*cnt[j]);
                
                p[(i+j)%m]=(p[(i+j)%m]+now);
            }
            
            int idx=(i+i)%m;
            
            p[idx]=(p[idx]+add);x[i]=cnt[i];
            
        //  out.println(res);
        }
        
        for(int i=0;i<m;i++)
        {
            long now=(i+i+i)%m;
            
            if(now==0)
            {
                res=(res+c3(cnt[i]));
            }
        }
        
        out.println(res);out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
    
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
    
    public String next() throws Exception {
        return nextToken().toString();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply