Concepts Used:
Sorting
Difficulty Level:
Medium
Problem Statement (Simplified):
You’re provided an array containing
Nelements, you have to answerqqueries. In each query, you’re provided withxandy. Print the sum of all values less thanxand greater thany.
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
xand greater thany. 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
xandy.2) But traversing will again create the issue discussed in the above approach. So we create a
Cumulative Sum Arrayfor the above array, where the value at indexireturns the sum of all values beforeith 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
xand ay, so if we findlower boundofxin a given array, we can get sum of elements smaller thanxfrom cumulative sum array. Also, if we find theupper boundofyin the given array, we can get sum of the elements greater thanyfrom the cumulative sum array.5) For sum of values greater than
y, we subtract the sum of values from0toupper boundofyfrom the total sum of the array.6) We then add them together and print the final sum.
Example:
Lets assume given array
Ais[5, 6, 2, 3, 4, 2, 3].We sort the array, after which array
Abecomes[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
3and5as a query. We search for lower bound of3in arrayA, i.e.1, so we addSumArr[1]to ourfinalSum.finalSumbecomes4.Now, we find upper bound of
5in arrayA, i.e.6. ButSumArr[6]contains sum of all numbers from0th index to6th index. But we need sum from6th index onwards only, so we substractSumArr[5]from total sum of array i.e.SumArr[6]. So elements from index6onwards have25-19i.e. 6 as sum. Finally we add this to ourfinalSum,finalSum = 6+4 => 10. Hence, our final answer to given query is10.
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