Given a sorted array arr[], and a set Q having M queries, where each query has values X and Y, the task is to find the sum of all integers less than X and greater than Y present in the array. Note: X and Y may or may not be present in the array.
Examples:
Input: arr[] = [3 5 8 12 15], Q = {{5, 12}, {4, 8}}
Output: 18 30
Explanation: For query 1, X = 5 and Y = 12. Sum = 3( < 5) + 15( > 12) = 18. For query 2, X = 4 and Y = 8. Sum = 3( < 4) + 15 ( > 8) + 12 ( > 8) = 30.Input: arr[] = [4 7 7 12 15], Q = {{3, 8}, {4, 8}}
Output: 27 27
Explanation: For query 1, X = 3 and Y = 8. Sum = 12( > 8) + 15 ( > 8) = 27. For query 2, Sum = 12 + 15 = 27.
Approach:
- Build a prefix sum array where prefix_sum[i] denotes the sum of arr[0] + arr[1] + … arr[i].
- Find the last index i which has a value less than X and extract the prefix sum up to the ith index. The index can be obtained in O(logN) complexity by using bisect_left() or lower_bound() in Python and C++ respectively..
- Similarly, find the first index i in the array with a value greater than Y and calculate the sum prefix_sum[n-1] – prefix_sum[i-1]. Inbuilt functions bisect() and upper_bound() in Python and C++ respectively, perform the required operation in O(logN).
- Sum of the two results calculated in the above two steps is the required answer. Keep repeating these steps for every query.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>using namespace std;int* createPrefixSum(int ar[], int n) { // Initialize prefix sum array int* prefix_sum = new int[n]; // Initialize prefix_sum[0] by ar[0] prefix_sum[0] = ar[0]; // Compute prefix sum for all indices for (int i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i-1] + ar[i]; } return prefix_sum;}int sumLessThanX(int ar[], int x, int prefix_sum[], int n) { // Index of the last element which is less than x int i = 0; while (i < n && ar[i] < x) { i++; } // If no element is less than x if (i == n) { return 0; } return prefix_sum[i-1];}int sumGreaterThanY(int ar[], int y, int prefix_sum[], int n) { // Index of the first element which is greater than y int i = n-1; while (i >= 0 && y < ar[i]) { i--; } // If no element is greater than y if (i < 0) { return 0; } return prefix_sum[n-1] - prefix_sum[i];}void solve(int ar[], int x, int y, int prefix_sum[], int n) { int ltx = sumLessThanX(ar, x, prefix_sum, n); int gty = sumGreaterThanY(ar, y, prefix_sum, n); // printing the final sum cout << ltx + gty << endl;}void print_l(int lb, int ub) { cout << "sum of integers less than " << lb << " and greater than " << ub << " is ";}int main() { // example 1 int ar[] = {3, 6, 6, 12, 15}; int n = sizeof(ar) / sizeof(ar[0]); int* prefix_sum = createPrefixSum(ar, n); // for query 1 int q1x = 5; int q1y = 12; print_l(q1x, q1y); solve(ar, q1x, q1y, prefix_sum, n); // for query 2 int q2x = 7; int q2y = 8; print_l(q2x, q2y); solve(ar, q2x, q2y, prefix_sum, n); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG {static int[] createPrefixSum(int []ar,int n){ // Initialize prefix sum // array int prefix_sum[]= new int[n]; // Initialize prefix_sum[0] // by ar[0] prefix_sum[0] = ar[0]; // Compute prefix sum for // all indices for(int i=1;i<n;i++){ prefix_sum[i] = prefix_sum[i-1]+ar[i]; } return prefix_sum;}// Function to return sum of all// elements less than Xstatic int sumLessThanX(int []ar,int x,int []prefix_sum){ // Index of the last element // which is less than x int i = 0; while(i<ar.length && ar[i]<x){ i++; } // If no element is less than x if(i==ar.length) return 0; return prefix_sum[i-1];}// Function to return sum of all// elements greater than Ystatic int sumGreaterThanY(int []ar, int y,int[] prefix_sum){ // Index of the first element // which is greater than y int i=ar.length-1; while(i>=0 && y<ar[i]){ i--; } // If no element is greater than y if(i<0){ return 0; } return prefix_sum[prefix_sum.length-1]-prefix_sum[i];}static void solve(int []ar, int x, int y, int []prefix_sum){ int ltx = sumLessThanX(ar, x, prefix_sum); int gty = sumGreaterThanY(ar, y, prefix_sum); // printing the final sum System.out.println(ltx + gty); }static void print_l(int lb, int ub){ System.out.print("sum of integers less than " + lb + " and greater than " + ub + " is "); } public static void main (String[] args) { // example 1 int ar[] = {3, 6, 6, 12, 15}; int n = ar.length; int []prefix_sum = createPrefixSum(ar, n); // for query 1 int q1x = 5; int q1y = 12; print_l(q1x, q1y); solve(ar, q1x, q1y, prefix_sum); // for query 2 int q2x = 7; int q2y = 8; print_l(q2x, q2y); solve(ar, q2x, q2y, prefix_sum); }}// This code is contributed by aadityaburujwale. |
Python3
# Python code for the above programfrom bisect import bisect, bisect_leftdef createPrefixSum(ar, n): # Initialize prefix sum # array prefix_sum = [0]*n # Initialize prefix_sum[0] # by ar[0] prefix_sum[0] = ar[0] # Compute prefix sum for # all indices for i in range(1, n): prefix_sum[i] = prefix_sum[i-1]+ar[i] return prefix_sum# Function to return sum of all# elements less than Xdef sumLessThanX(ar, x, prefix_xum): # Index of the last element # which is less than x pos_x = bisect_left(ar, x) - 1 if pos_x >= 0 : return prefix_sum[pos_x] # If no element is less than x else: return 0# Function to return sum of all# elements greater than Ydef sumGreaterThanY(ar, y, prefix_sum): # Index of the first element # which is greater than y pos_y = bisect(ar, y) pos_y -= 1 if pos_y < len(ar)-1 : return prefix_sum[-1]-prefix_sum[pos_y] # If no element is greater than y else: return 0def solve(ar, x, y, prefix_sum): ltx = sumLessThanX(ar, x, prefix_sum) gty = sumGreaterThanY(ar, y, prefix_sum) # printing the final sum print(ltx + gty) def print_l(lb, ub): print("sum of integers less than {}".format(lb) + " and greater than {} is ".format(ub), end = '')if __name__ == '__main__': # example 1 ar = [3, 6, 6, 12, 15] n = len(ar) prefix_sum = createPrefixSum(ar, n) # for query 1 q1x = 5 q1y = 12 print_l(q1x, q1y) solve(ar, q1x, q1y, prefix_sum) # for query 2 q2x = 7 q2y = 8 print_l(q2x, q2y) solve(ar, q2x, q2y, prefix_sum) |
C#
// C# code for the above programusing System;class GFG {static int[] createPrefixSum(int[] ar,int n){// Initialize prefix sum // array int[] prefix_sum= new int[n]; // Initialize prefix_sum[0] // by ar[0] prefix_sum[0] = ar[0]; // Compute prefix sum for // all indices for(int i=1;i<n;i++){ prefix_sum[i] = prefix_sum[i-1]+ar[i]; } return prefix_sum;}// Function to return sum of all// elements less than Xstatic int sumLessThanX(int[] ar,int x,int[] prefix_sum){ // Index of the last element // which is less than xint i = 0; while(i<ar.Length && ar[i]<x){ i++; }// If no element is less than xif(i==ar.Length) return 0; return prefix_sum[i-1];}// Function to return sum of all// elements greater than Ystatic int sumGreaterThanY(int[] ar, int y,int[] prefix_sum){ // Index of the first element // which is greater than yint i=ar.Length-1;while(i>=0 && y<ar[i]){ i--;}// If no element is greater than yif(i<0){ return 0;}return prefix_sum[prefix_sum.Length-1]-prefix_sum[i];}static void solve(int []ar, int x, int y, int []prefix_sum){ int ltx = sumLessThanX(ar, x, prefix_sum); int gty = sumGreaterThanY(ar, y, prefix_sum); // printing the final sum Console.WriteLine(ltx + gty);}static void print_l(int lb, int ub){ Console.Write("sum of integers less than " + lb + " and greater than " + ub + " is ");} static public void Main () { // example 1 int[] ar = {3, 6, 6, 12, 15}; int n = ar.Length; int[] prefix_sum = createPrefixSum(ar, n); // for query 1 int q1x = 5; int q1y = 12; print_l(q1x, q1y); solve(ar, q1x, q1y, prefix_sum); // for query 2 int q2x = 7; int q2y = 8; print_l(q2x, q2y); solve(ar, q2x, q2y, prefix_sum); }}// This code is contributed by Aman Kumar. |
Javascript
function createPrefixSum(ar) { // Initialize prefix sum array const prefix_sum = new Array(ar.length); // Initialize prefix_sum[0] by ar[0] prefix_sum[0] = ar[0]; // Compute prefix sum for all indices for (let i = 1; i < ar.length; i++) { prefix_sum[i] = prefix_sum[i-1] + ar[i]; } return prefix_sum;}// Function to return sum of all elements less than Xfunction sumLessThanX(ar, x, prefix_sum) { // Index of the last element which is less than x let i = 0; while (i < ar.length && ar[i] < x) { i++; } // If no element is less than x if (i == ar.length) { return 0; } return prefix_sum[i-1];}// Function to return sum of all elements greater than Yfunction sumGreaterThanY(ar, y, prefix_sum) { // Index of the first element which is greater than y let i = ar.length-1; while (i >= 0 && y < ar[i]) { i--; } // If no element is greater than y if (i < 0) { return 0; } return prefix_sum[prefix_sum.length-1] - prefix_sum[i];}function solve(ar, x, y, prefix_sum) { const ltx = sumLessThanX(ar, x, prefix_sum); const gty = sumGreaterThanY(ar, y, prefix_sum); // Printing the final sum console.log(ltx + gty);}function print_l(lb, ub) { console.log("sum of integers less than " + lb + " and greater than " + ub + " is ");}// example 1const ar = [3, 6, 6, 12, 15];const prefix_sum = createPrefixSum(ar);// for query 1const q1x = 5;const q1y = 12;print_l(q1x, q1y);solve(ar, q1x, q1y, prefix_sum);// for query 2const q2x = 7;const q2y = 8;print_l(q2x, q2y);solve(ar, q2x, q2y, prefix_sum); |
Output:
sum of integers less than 5 and greater than 12 is 18 sum of integers less than 7 and greater than 8 is 42
Time Complexity: O(N + (M * logN))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!