#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?

CodePudding user response：

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 solition is o(n^3) worst case.

CodePudding user response：

You only need to look at a sliding window of three consecutive integers in linear time and constant memory. Here's Ruby code that does this.

def consecutive_triplets(arr)
  s = 0
  num_triplets = 0
  0.upto(arr.length - 1) do |i|
    s  = arr[i]
    s -= arr[i-3] if i >= 3
    num_triplets  = 1 if s % 3 == 0 && i >= 2
  end
  return num_triplets
end