M72SOP - Editorial

PROBLEM LINK:

Practice

Contest

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.

//