sgoel01's blog

Sum of multiplication of distance and maximum value for each pair in an Integer Array
By sgoel01, history, 10 years ago, In English

Given an unsorted Integer array with their values. Need to calculate sum of Multiplication of Distance between each pair and The value that is maximum between them.

To be more clear. Lets say array A[] with n elements

Calculate:-


for all i & j (i<j)
sum (distance(i,j)*(max(A[i],A[j])))

O(n^2) is easy. I want better than that. I've tried hard but don't know what data structure to use. I would request to give only a hint to solve this problem ( I will try from there )

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

This problem isn't very difficult.
My hint for you: for each i find all pairs if indexes in which the distance if multiplied by a[i]. This can be done effectively.

PS.
Can your give the link to this problem?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Someone asked me to solve this. Don't have link for this problem. The hint you gave is not clear. Can you elaborate a little.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      For each i find all j > i such as a[i] >= a[j]. And you should add to the answer this value: a[i] * (j1 — i) + a[i] * (j2 — i) + ... + a[i] * (jk — i) = a[i] * (j1 — i + j2 — i + ... + jk — i). This sum can be found effectively (for example using Fenwick tree).

      → Reply