Find sum of elements less than A and greater than B in an array

Concepts Used:

Sorting

Difficulty Level:

Medium

Problem Statement (Simplified):

You're provided an array containing N elements, you have to answer q queries. In each query, you're provided with x and y. Print the sum of all values less than x and greater than y.

See original problem statement here

Test case:

Input:
5
5 8 3 15 12
2
5 12
4 8

Output:
18
30

Explanation:
Query-1:
There is 1 element which is less than 5, i.e. 3. So we add 3 to sum.
There 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.

Query-2:
There is 1 element which is less than 4, i.e. 3. So we add 3 to sum.
There 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.

Solving Approach :

Bruteforce Approach:

1) We can iterate over all elements and add all values which are less than x and greater than y. Finally, print the sum as an answer to the query.

2) This approach takes O(N) 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 on getting some idea from programming languages online course.

Efficient Approach:

Lower Bound of a number N 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.

Upper Bound of a number N 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.

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 and y.

2) But traversing will again create the issue discussed in the above approach. So we create a Cumulative Sum Array for the above array, where the value at index i returns the sum of all values before ith index in the array.

3) After we have created a cumulative sum array, now we have to answer queries.

4) For each query, we have an x and a y, so if we find lower bound of x in a given array, we can get sum of elements smaller than x from cumulative sum array. Also, if we find the upper bound of y in the given array, we can get sum of the elements greater than y from the cumulative sum array.

5) For sum of values greater than y, we subtract the sum of values from 0 to upper bound of y from the total sum of the array.

6) We then add them together and print the final sum.

Example:

  • Lets assume given array A is [5, 6, 2, 3, 4, 2, 3].

  • We sort the array, after which array A becomes [2, 2, 3, 3, 4, 5, 6].

  • 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].

  • Lets assume we get 3 and 5 as a query. We search for lower bound of 3 in array A, i.e. 1, so we add SumArr[1] to our finalSum. finalSum becomes 4.

  • Now, we find upper bound of 5 in array A, i.e. 6. But SumArr[6] contains sum of all numbers from 0th index to 6th index. But we need sum from 6th index onwards only, so we substract SumArr[5] from total sum of array i.e. SumArr[6]. So elements from index 6 onwards have 25-19 i.e. 6 as sum. Finally we add this to our finalSum, finalSum = 6+4 => 10. Hence, our final answer to given query is 10.

Solutions:

#include <stdio.h>
#include<stdlib.h>

int lowerBound(long long array[], int length, long value) {
    int low = 0;
    int high = length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (value <= array[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}
int upperBound(long long array[], int length, long value) {
    int low = 0;
    int high = length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (value >= array[mid]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int compare(const void * a, const void * b) 
{ 
    return ( *(int*)a - *(int*)b ); 
} 


int main(){   
    int n;
    scanf("%d",&n);
    long long arr[n];
    long long sum[n];
    for(int i=0;i<n;i++)
     scanf("%lld",&arr[i]);

    qsort((void*)arr, n, sizeof(arr[0]), compare); 

    sum[0]=arr[0];
    for(int i=1;i<n;i++)
     sum[i]=sum[i-1] + arr[i];

    int q;
    scanf("%d",&q);
    while(q--){
       int x,y;
       scanf("%d%d",&x,&y);
       long long ans=0;    
       int xind=lowerBound(arr,n,x);
       int yind=upperBound(arr,n,y);
       if(xind !=0 && yind !=n)
        ans=sum[xind-1] + (sum[n-1]-sum[yind-1]);
       else if(xind==0 && yind !=n)
        ans=(sum[n-1]-sum[yind-1]);
       else if(xind!=0 && yind ==n)
        ans=sum[xind-1];
             printf("%lld\n",ans);

      }
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int lowerBound(long long array[], int length, long value) {
    int low = 0;
    int high = length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (value <= array[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}
int upperBound(long long array[], int length, long value) {
    int low = 0;
    int high = length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (value >= array[mid]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main(){   
    int n;
    cin>>n;
    long long arr[n];
    long long sum[n];
    for(int i=0;i<n;i++)
     cin>>arr[i];
    sort(arr,arr+n);

    sum[0]=arr[0];
    for(int i=1;i<n;i++)
     sum[i]=sum[i-1] + arr[i];

    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
         long long ans=0;    
         int xind=lowerBound(arr,n,x);
         int yind=upperBound(arr,n,y);
         if(xind !=0 && yind !=n)
          ans=sum[xind-1] + (sum[n-1]-sum[yind-1]);
         else if(xind==0 && yind !=n)
          ans=(sum[n-1]-sum[yind-1]);
         else if(xind!=0 && yind ==n)
          ans=sum[xind-1];

     cout<<ans<<"\n";

      }
}
import java.util.*;
import java.io.*;
public class Main{

  public static int lowerBound(long[] array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = (low + high) / 2;
            if (value <= array[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    public static int upperBound(long[] array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = (low + high) / 2;
            if (value >= array[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    public static void main(String args[]){

        Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));

        int n=in.nextInt();

        long arr[]=new long[n];
        long sum[]=new long[n];


        for(int i=0;i<n;i++){
             arr[i]=in.nextLong();
        }
        Arrays.sort(arr); 
        sum[0]=arr[0];
        for(int i=1;i<n;i++)
        sum[i]=sum[i-1] + arr[i];

      int q=in.nextInt();

     while(q-- >0){
         long x=in.nextLong();
         long y=in.nextLong();

     long ans=0;    
     int xind=lowerBound(arr,n,x);
     int yind=upperBound(arr,n,y);
     if(xind !=0 && yind !=n)
      ans=sum[xind-1] + (sum[n-1]-sum[yind-1]);
     else if(xind==0 && yind !=n)
      ans=(sum[n-1]-sum[yind-1]);
     else if(xind!=0 && yind ==n)
      ans=sum[xind-1];
        System.out.println(ans);
    }
  }
}
Previous post Find the misplaced elements
Next post Sort array containing only 0, 1 and 2 as elements

Leave a Reply

Your email address will not be published. Required fields are marked *