I need to compute the summation of:$$\left\lfloor\frac{\text{sum of triplets}}{\text{product of triplets}}\right\rfloor$$from integers of an array.Input:51 2 1 7 3Output:6Explanation:The following triplets exists in the given array:1 2 11 2 71 2 31 1 71 1 31 7 32 1 72 1 32 7 31 7 3Considering these triplets from the sample input:1 2 1 contributes 2 [floor{(1+2+1)/(1*2*1)} = floor{4/2}=2]1 2 3 contributes 11 1 7 contributes 11 1 3 contributes 12 1 3 contributes 1All other triplets contribute 0 to the sum.Hence the answer is (2+1+1+1+1)=6.What I tried has complexity \$O(n^3)\$:#include <iostream>#include <cmath>using namespace std;int main(){    long t,n[300005],sum=0,mul=1,i,j,k,res=0;    cin >> t;    for(i=0;i<t;i++)        cin >>n[i];    for(i=0;i<t-2;i++)    for(j=i+1;j<t-1;j++)    for(k=j+1;k<t;k++)    {        sum = n[i]+n[j]+n[k];        mul = n[i]*n[j]*n[k];        res += floor(sum/mul);    }    cout << res << endl;    return 0;}Is there any hint of better optimization?
Optimize triplet summation
c++;performance
Can be done in \$O(n)\$ timeYou can do better than \$O(n^3)\$ if you think about what kinds of triplets give nonzero contributions.  First of all, any triplet that does not contain a 1 will contribute zero to the final answer.  Next, if you examine all the triplets that contain 1, there are 5 types of triplets that contribute nonzero amounts to the answer:1 1 1 contributes 31 1 2 contributes 21 1 X contributes 1, where X > 21 2 2 contributes 11 2 3 contributes 1 So you can get an \$O(n)\$ solution by counting all the 1s 2s and 3s in the input.  Then you can compute the number of each of the 5 types of triplets above by using simple combinatorics.Sample \$O(n)\$ solutionHere is a sample solution based on the above.  Notice I removed the entire input array because all that is needed is the counts:#include <iostream>int main(){    long n   = 0;    long c1  = 0;    long c2  = 0;    long c3  = 0;    long res = 0;    std::cin >> n;    for(long i=0;i<n;i++) {        long num;        std::cin >> num;        if (num == 1)            c1++;        else if (num == 2)            c2++;        else if (num == 3)            c3++;    }    // Count all the {1, 1, 1} triplets.  There are (c1 choose 3),    // each contributing 3:    res += ((c1 * (c1-1) * (c1-2)) / 6) * 3;    // Count all the {1, 1, 2} triplets.  There are (c1 choose 2) * c2    // combinations, each contributing 2:    res += ((c1 * (c1-1)) / 2) * c2 * 2;    // Count all the {1, 1, X} triplets, where X > 2.  There are    // (c1 choose 2) * (n - c1 - c2) combinations, each contributing 1:    res += ((c1 * (c1-1)) / 2) * (n - c1 - c2);    // Count all the {1, 2, 2} triplets.  There are c1 * (c2 choose 2)    // combinations, each contributing 1:    res += c1 * ((c2 * (c2-1)) / 2);    // Count all the {1, 2, 3} triplets.  There are c1 * c2 * c3    // combinations, each contributing 1:    res += c1 * c2 * c3;    std::cout << res << std::endl;    return 0;}Of course, this program can be optimized even further by combining some of the expressions, but I wrote it in the way that most clearly demonstrates where each part of the answer came from.