Vasiljko's blog

Sum of all absolute values in two arrays
By Vasiljko, history, 8 years ago, In English

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)?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Vasiljko (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please problem link ?

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

We can first sort both arrays ----O(nlogn)

Now we can find in how pairs each element will be greater element(we add this many times ot the sum) and in how many it will be smaller one using binary search. We do this for all elements(we subtract this many times from sum) --O(nlogn)(we can even do two pointers --O(n))

Total = O(nlogn)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of two pointers but couldn't implement it idk why, but binary search solution is not really clear to me. Can you post code? I would be really gratefull.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh i got it. Thank you so much <3 :)

    → Reply