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)/(121)} = 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 
#include 
using namespace std;

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

    for(i=0;i>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?

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

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> 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.

StackExchange Code Review Q#144274, answer score: 6