Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Sorting interview programming

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

Deepak

Last Updated on June 17, 2022 by Ria Pathak

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.

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);
    }
  }
}

def lowerBound(array, length, value):
	
	low = 0
	high = length
	
	while (low < high):
	
		mid = (low + high) // 2
	
		if (value <= array[mid]):
			high = mid
		
		else:
			low = mid + 1
		
	return low

def upperBound(array, length, value):
	
	low = 0
	high = length
	while (low < high):
		mid = (low + high) // 2
		if (value >= array[mid]):
			low = mid + 1
		else:
			high = mid
		
	return low

n = int(input())
sum = [0] * n
arr = list(map(int,input().split()))
arr.sort()
sum[0] = arr[0]

for i in range(1, n):
	sum[i] = sum[i-1] + arr[i]

q = int(input())

while(q):
	
	q -= 1
	x, y = map(int, input().split())
	ans = 0
	xind = lowerBound(arr, n, x)
	yind = upperBound(arr, n, y)
	
	if(xind != 0 and yind != n):
		ans = sum[xind-1] + (sum[n-1]-sum[yind-1]);
	
	elif(xind == 0 and yind != n):
		ans = (sum[n - 1] - sum[yind - 1])
	
	elif(xind != 0 and yind == n):
		ans = sum[xind - 1]
		
	print(ans)

[forminator_quiz id="1088"]

This article tried to discuss the concept of Sorting. Hope this blog helps you understand the concept of Sorting. To practice more problems you can check out MYCODE|competitive programming

Leave a Reply

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

Close

Related Post