How to even approach the problem

#1

please help with the approch

#2

@chemant077 In this problem, we need to find out for every number at index m in the given array the sum of all the numbers which appears at an index i where i < m and array[i] < array[m]. And add all these sums to the final answer

To solve this problem in a best-optimized way need to think something better than O(n*n). Here we will apply the concept of merge sort problem.
In merge sort, we divide the array into subarrays recursively until there are just 2 elements in a subarray. We then arrange the subarray in sorted order and merge it with other subarrays.

Consider 2 subarrays arr[l…mid-1] and arr[mid…r] in the merge function which are sorted seperately and are ready to merge

i varies from l to mid-1

j varies from mid to r

i<j always

Let sum be the variable which holds the sum of all the numbers previously seen on the stairs which are smaller than the present number.

if(arr[i]<arr[j])

arr[i] comes before arr[j] in the input array and arr[i] is less than arr[j]. So we have to add arr[i] to sum.

Since arr[i]<arr[j], arr[i]<(arr[j+1], arr[j+2],….,arr[r]) because the subarrays to be merged are sorted.

So on the whole (r-j+1) times of arr[i] is added to the sum.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.