Given an array A of n elements.
a_i denotes i th element. We have to find the sum -
(n) \times (a_1 \times a_1 + a_2 \times a_2 + \cdots +a_n \times a_n) +
(n - 1)(a_1 \times a_2 + a_2 \times a_3 + \cdots +a_{n-1} \times a_n) +
(n - 2)(a_1 \times a_3 + a_2 \times a_4 + \cdots +a_{n-2} \times a_n) + \cdots
\vdots
1 \leq n \leq 10^5
1 \leq a_i \leq 10^9
How to solve it? Please help
2 Likes
You can make a prefix sum of the array A and also store the sum of the series
S = a1 + 2 \times a2 + … + n \times an
If we take the first term of each term of the sum, it can be written as
n \times a1 (a1 + a2 + . . .+ an) - a1 (a2 + 2 \times a3 + … + (n - 1) \times an)
Its first term can be calculated in O(1) using prefix sum and the second term can be calculated by subtracting sum of all the elements from S. So now S becomes
S = a2 + 2 \times a3 + … + (n - 1) \times an
Now we calculate second term of each term of the sum which is
n \times a2 (a2 + a3 + . . .+ an) - a2 (a3 + 2 \times a4 + … + (n - 2) \times an)
which again can be calculated in O(1) using prefix sum for the first term and subtracting that sum from S. This should be done for every element in the sum. So the entire solution becomes O(n).
If you still have a doubt feel free to ask. Hope this helps.
3 Likes
Purely Brilliant. Nice Math
Thanks for nicely explained and beautiful answer