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.
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).
Thanks for replying, although your explanation does provide an intuition to why this is happening but can you also provide a proof as to why it is actually happening?
https://en.wikipedia.org/wiki/Rule_of_product