Sum of all absolute values in two arrays

Revision en2, by Vasiljko, 2017-05-21 23:47:52

Given two arrays A and B of size N. Let's take A={4,2,8} AND B={2,7,3}. All possible absolute values are 1: |4-2|+|4-7|+|4-3|=6 ; 2: |2-2|+|2-7|+|2-3|=6 ; 3: |8-2|+|8-7|+|8-3|=12; Sum of all these is 6+6+12=24;

Constraints : 1<=N<=10^5 , |Ai|,|Bi|<=10^6, so Ai,Bi can be negative

Any help with solution with time complexity O(nlogn)?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Vasiljko 2017-05-21 23:47:52 45 Tiny change: '\nAny help? ' -> '\nAny help with solution with time complexity O(nlogn)?'
en1 English Vasiljko 2017-05-21 23:46:27 339 Initial revision (published)