abbi_18's blog

By abbi_18, history, 8 years ago, In English

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.

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

»
8 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Basically, once you have fixed i and j, you can choose any number of items lying before i (0 to i-1), and any number of items lying after j (0 to n-j), but no item lying between i and j.

You have the option of choosing 0,1,2...i-1 numbers from the left side of the ith number and the option of choosing 0,1,2..n-j numbers from the right side of the jth number. Also note that these choices are independent of each other.

Hence, the required answer is i*(n-j+1).