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

Revision en2, by 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.

#### History

Revisions

Rev. Lang. By When Δ Comment
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)