# Multiplying array elements

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.

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

• 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. – Mahatma Gandhi Jun 7 '15 at 18:13

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$

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

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?