PROBLEM LINK:
Author: manjunath1996
Tester: nmalviya1929
Editorialist: vinod10
DIFFICULTY:
Simple
PREREQUISITES:
Basic programming.
PROBLEM:
Array of N elements is given. Find sum of product of all pairs (A[i],A[j]) such that i>j.
QUICK EXPLANATION:
For each array element A[i] we take its product with A[i+1],…,A[N] and add it to the answer.
EXPLANATION:
O(N2) approach:
We can iterate through all the possible pairs and calculate the answer.
ans=0
for all A[i] where i=1,2,…,N-1
for all A[j] where j=i+1,i+2,.....,N
ans=ans+A[i]*A[j]
O(N) approach:
Though this approach is not required as O(TN2) easily passes the test cases, you should know this approach.
For every ‘i’ all possible pairs are (i,i+1),(i,i+2),…,(i,N).
So sum of products is A[i]*A[i+1] + … + A[i]*A[N] = A[i] * (A[i+1]+…+A[N])
Hence we can precompute cumulative sum from the end as:
sum[N]=0;
for(i = N-1; i>0; --i)
sum[i]=sum[i+1]+a[i+1];
So final answer will be summation of A[i]*sum[i] for all i.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.