Find triplets such that their sum is divisible by 3. Can this be solved in O(n^2) or any other optimization?

Question

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

int main() {
// your code goes here
vector<int> arr={0,2,3,4};
int count=0;

int n = arr.size();
for(int i=0;i<n-2;i++)
{
    for(int j=i+1;j<n-1;j++)
    {
        for(int k=j+1;k<n;k++)
        {
            if(i+1==j && j+1==k)
            {
                if((arr[i]+arr[j]+arr[k])%3==0)
                {
                    count++;
                }
            }
        }
    }
}
cout<<count<<" ";
return 0;
}

This solution is O(n^3) for generating triplets whose average is divisible by 3 and elements of triplets must be consecutive.How to optimize this solution?

Answer 1

1. Separate your numbers in three tables according to their value modulo 3 (their sizes are n0,n1 and n2). This is o(n)

2. the triplets answer to your questions are:

   a) three numbers with the same value modulo 3 o(C(3,n0)+C(3,n1)+C(3,n2)) = o(n^3) max if n0=n1=n2=n/3

   b) one number equal 0, the other 1 the third 2 and permutations o(n0n1n2) = o(n^3) max if n0=n1=n2=n/3

This is o(n^3) because the number of solutions is o(n^3) worst case.