{"id":1078,"date":"2020-06-11T10:24:17","date_gmt":"2020-06-11T10:24:17","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1078"},"modified":"2022-06-17T05:24:09","modified_gmt":"2022-06-17T05:24:09","slug":"find-sum-of-elements-less-than-a-and-greater-than-b-in-an-array","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-sum-of-elements-less-than-a-and-greater-than-b-in-an-array\/","title":{"rendered":"Find sum of elements less than A and greater than B in an array"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

You’re provided an array containing N<\/code> elements, you have to answer q<\/code> queries. In each query, you’re provided with x<\/code> and y<\/code>. Print the sum of all values less than x<\/code> and greater than y<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test case:<\/h4>\n
Input:\n5\n5 8 3 15 12\n2\n5 12\n4 8\n\nOutput:\n18\n30\n\nExplanation:\nQuery-1:\nThere is 1 element which is less than 5, i.e. 3. So we add 3 to sum.\nThere is 1 element which is greater than 12 i.e. 15. So we add 15 to sum. Our final sum is 15+3 i.e. 18, so we print 18 as our answer.\n\nQuery-2:\nThere is 1 element which is less than 4, i.e. 3. So we add 3 to sum.\nThere are 2 elements that are greater than 8 that are 12 and 15. So we add 15 and 12 to sum. Our final sum is 12+15+3 i.e. 30, so we print 30 as our answer.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/em><\/strong><\/p>\n
\n
1) We can iterate over all elements and add all values which are less than x<\/code> and greater than y<\/code>. Finally, print the sum as an answer to the query.<\/p>\n
2) This approach takes O(N)<\/code> time for each query, which is efficient if we have a very low amount of queries. But when we have a large number of queries this approach is highly inefficient. So we move towards a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/em><\/strong><\/p>\n
\n
Lower Bound of a number N<\/em><\/strong> in any sorted array returns the last index at which the number smaller than or equal to N lies. Index next to it contains a number greater than N.<\/p>\n
Upper Bound of a number N<\/em><\/strong> in any sorted array returns the first index at which the number greater than or equal to N lies. The index previous to it contains the number smaller than N.<\/p>\n
1) If we sort the elements in a non-decreasing manner, it would be easy to find sum as we can then traverse from both ends and stop when numbers go beyond the range of x<\/code> and y<\/code>.<\/p>\n
2) But traversing will again create the issue discussed in the above approach. So we create a Cumulative Sum Array<\/code> for the above array, where the value at index i<\/code> returns the sum of all values before i<\/code>th<\/sup> index in the array.<\/p>\n
3) After we have created a cumulative sum array, now we have to answer queries.<\/p>\n
4) For each query, we have an x<\/code> and a y<\/code>, so if we find lower bound<\/code> of x<\/code> in a given array, we can get sum of elements smaller than x<\/code> from cumulative sum array. Also, if we find the upper bound<\/code> of y<\/code> in the given array, we can get sum of the elements greater than y<\/code> from the cumulative sum array.<\/p>\n
5) For sum of values greater than y<\/code>, we subtract the sum of values from 0<\/code> to upper bound<\/code> of y<\/code> from the total sum of the array.<\/p>\n
6) We then add them together and print the final sum.<\/p>\n<\/blockquote>\n
Example:<\/h4>\n
\n
    \n
  • \n
    Lets assume given array A<\/code> is [5, 6, 2, 3, 4, 2, 3]<\/code>.<\/p>\n<\/li>\n
  • \n
    We sort the array, after which array A<\/code> becomes [2, 2, 3, 3, 4, 5, 6]<\/code>.<\/p>\n<\/li>\n
  • \n
    Now, we create prefix sum array for above array, where every index has sum of element at that index and all elements before it, so prefix sum array for above array is SumArr = [2, 4, 7, 10, 14, 19, 25]<\/code>.<\/p>\n<\/li>\n
  • \n
    Lets assume we get 3<\/code> and 5<\/code> as a query. We search for lower bound of 3<\/code> in array A<\/code>, i.e. 1<\/code>, so we add SumArr[1]<\/code> to our finalSum<\/code>. finalSum<\/code> becomes 4<\/code>.<\/p>\n<\/li>\n
  • \n
    Now, we find upper bound of 5<\/code> in array A<\/code>, i.e. 6<\/code>. But SumArr[6]<\/code> contains sum of all numbers from 0<\/code>th<\/sup> index to 6<\/code>th<\/sup> index. But we need sum from 6<\/code>th<\/sup> index onwards only, so we substract SumArr[5]<\/code> from total sum of array i.e. SumArr[6]<\/code>. So elements from index 6<\/code> onwards have 25-19<\/code> i.e. 6 as sum. Finally we add this to our finalSum<\/code>, finalSum = 6+4  => 10<\/code>. Hence, our final answer to given query is 10<\/code>. <\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
    Solutions:<\/h3>\n\t\t\t\t\t\t