All Pair of sum

Revision en2, by Aakas_kumar, 2024-01-09 17:48:15

Hi folk: I know it is not a very hard concept like HLD and merging in the trees and all but for the junta that is below specialist/people but it could give a great inside when you ask all pair sum problems it could be a subproblem of the hard and bigger problem.

here is code for O(n^2)

int sum=0; vector v(n); for(int i=0; i<n; i++){ for(int j= i+1; j<n; j++){ sum+= v[i]*v[j]; } }

so here is the code for the O(n)

int sum=0; int sq_sum=0; for(int i=0; i<n; i++){ sum+=v[i]; sq_sum+= v[i]*v[i]; } int ans = (sum*sum — sq_sum)/2 ; it may be a good concept

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Aakas_kumar 2024-01-10 11:37:59 18
en2 English Aakas_kumar 2024-01-09 17:48:15 6
en1 English Aakas_kumar 2024-01-09 17:44:38 630 Initial revision (published)