here is the link of the code https://ide.codingblocks.com/s/72608
last testcase is not passing
One test case not clearing of alpha score
Hi
Approach for this question is like this
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.
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.