0
$\begingroup$

We are given a sorted array containing elements at indices $x_1,x_2,x_3,x_4,....x_n$.

We have to find the product $\displaystyle\sum_{i,j,k}x_ix_jx_k$ where $j\geqslant i$ and $k\geqslant j$. For example, in an array $\{1,2,3\}$, the product would involve terms like

1*1*1,    1*1*2,    1*1*3,    1*2*2,    1*2*3,    2*2*2,    2*2*3,    2*3*3,
3*3*3,

The answer would be the summation of the above terms.

I need an efficient algorithm which can extend to the generic case of $\displaystyle\sum_{i,j,k,l\cdots}x_ix_jx_k\cdots$.

I have found a solution by brute forcing but I can't find an efficient algorithm to do the same.

$\endgroup$
2
$\begingroup$

Total ways to do it is $^{n}{\mathbb C}_3$. Java:

int[] array = new int[]{1,2,3,4,5};
int sum =0;
for(int i=0;i<array.length;i++){
    for(int j=i+1;j<array.length;j++){
        for(int k=j+1;k<array.length;k++){
            sum+=array[i]*array[j]*array[k];
        }
    }
}
System.out.println(sum);
$\endgroup$
  • $\begingroup$ That is the brute force method. I am looking for a faster algorithm which can also do a summation while multiplying x1,...xn instead of just 3 elements. $\endgroup$ – Mahatma Gandhi Jun 7 '15 at 18:13
0
$\begingroup$

HINT: $$\left(\sum_ix_i\right)^3=6\sum_{i<j<k}x_ix_jx_k+3\sum_{i<j}x_i^2x_j+3\sum_{i<j}x_ix_j^2+\sum_ix_i^3\\ \sum_ix_i\sum_jx_j^2=\sum_{i<j}x_i^2x_j+\sum_{i<j}x_ix_j^2+\sum_ix_i^3$$
You want $\sum_{i<j<k}x_ix_jx_k+\sum_{i<j}(x_i^2x_j+x_ix_j^2)+\sum_ix_i^3$

$\endgroup$
  • $\begingroup$ Would this be easily extendable to ∑(xi * xj * xk * ..) where j>=i,k>=j,l>=k .. and so on? $\endgroup$ – Mahatma Gandhi Jun 7 '15 at 18:54
  • $\begingroup$ I think it would be tricky beyond four or five factors. $\endgroup$ – Empy2 Jun 7 '15 at 19:10
0
$\begingroup$

Just expand the sums and you will see the general pattern: $$ \sum_{i,j,k} = x_1*(\sum_{j\ge1,k\ge1}x_jx_k + \sum_{j\ge2,k\ge2}x_jx_k + \sum_{j\ge3,k\ge3}x_jx_k + \ldots)\\ + x_2*(\sum_{j\ge2,k\ge2}x_jx_k + \sum_{j\ge3,k\ge3}x_jx_k + \ldots)\\ + x_3*(\sum_{j\ge3,k\ge3}x_jx_k + \ldots)\\ + \ldots. $$ Note further that the innermost sums ($\sum_{k\ge k_0}x_k$) occur multiple times, so you can precompute those and, in fact, multiply them by $x_j=x_{k_0}$ while you're at it.

Call those partial sums $P_k$.

Then your problem transforms into computing $$ x_1*(P_1+P_2+P_3+\ldots+P_n)\\ +x_2*(P_2+P_3+\ldots+P_n)\\ +x_3*(P_3+\ldots+P_n)\\ +\ldots. $$

Note that this is $$ P_n*(x_1+x_2+\ldots+x_n)\ldots\\ +P_{n-1}*(x_2+\ldots+x_n)\ldots\\ +\ldots $$ and that the precomputed partial sums occur a second time, this time without the factor of $x_j$.

You thus go from O($n^3$) multiplications and additions to O($n$) additions and O($n$) multiplications, at the cost of O($n$) storage requirements for the partial sums.

Is this the sort of thing you had in mind?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.