Occurence of a pair in contigous subarrays of a given array.

Правка en2, от abbi_18, 2017-03-03 00:26:21

I was recently solving a problem on Hacker-Earth and there was a particular subtask I needed to complete to submit the solution successfully. Say, I am given an array of integers.pick a pair (i,j) such that 'i' is less than 'j'. The task was to find out the number of times this pair will occur in all the contiguous subarrays of the given array.

for example : number of elements — n = 5; given array — 1 2 3 4 5

subarrays of given array — (1,2) (2,3) (3,4) (4,5) (1,2,3) (2,3,4) (3,4,5) (1,2,3,4) (2,3,4,5) (1,2,3,4,5)

pair (1,2) occurs 4 number of times in subarrays (1,2) , (1,2,3) , (1,2,3,4) and (1,2,3,4,5); similirialy, pair (3,4) occurs 6 number of times in subarrays (3,4) , (2,3,4) , (3,4,5) , (1,2,3,4) , (2,3,4,5) , (1,2,3,4,5);

Now, I found that for every pair (i,j) such that i<j, can find it ** (n-j+1)*i ** number of times. Can anybody please explain with mathematical proof, why this particular expression is working?

Thank you.

Теги subarray, array, #implementation, formula

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский abbi_18 2017-03-03 00:26:21 0 (published)
en1 Английский abbi_18 2017-03-03 00:24:38 1063 Initial revision (saved to drafts)