Optimize triplet summation 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:

5

1 2 1 7 3


Output:

6


Explanation:


  The following triplets exists in the given array:
  
  1 2 1
  
  1 2 7
  
  1 2 3
  
  1 1 7
  
  1 1 3
  
  1 7 3
  
  2 1 7
  
  2 1 3
  
  2 7 3
  
  1 7 3
  
  Considering 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 1
  
  1 1 7 contributes 1
  
  1 1 3 contributes 1
  
  2 1 3 contributes 1
  
  All 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 &lt;iostream&gt;
#include &lt;cmath&gt;
using namespace std;

int main()
{
    long t,n[300005],sum=0,mul=1,i,j,k,res=0;
    cin &gt;&gt; t;

    for(i=0;i&lt;t;i++)
        cin &gt;&gt;n[i];


    for(i=0;i&lt;t-2;i++)
    for(j=i+1;j&lt;t-1;j++)
    for(k=j+1;k&lt;t;k++)
    {
        sum = n[i]+n[j]+n[k];
        mul = n[i]*n[j]*n[k];
        res += floor(sum/mul);
    }

    cout &lt;&lt; res &lt;&lt; endl;
    return 0;
}


Is there any hint of better optimization?
Can be done in \$O(n)\$ time

You 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 3
1 1 2 contributes 2
1 1 X contributes 1, where X &gt; 2
1 2 2 contributes 1
1 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)\$ solution

Here is a sample solution based on the above.  Notice I removed the entire input array because all that is needed is the counts:

#include &lt;iostream&gt;

int main()
{
    long n   = 0;
    long c1  = 0;
    long c2  = 0;
    long c3  = 0;
    long res = 0;

    std::cin &gt;&gt; n;
    for(long i=0;i&lt;n;i++) {
        long num;
        std::cin &gt;&gt; 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 &gt; 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 &lt;&lt; res &lt;&lt; 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.