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

Efficient approach

Before moving to the approach, let’s learn lower_bound and upper_bound functions:

Lower_bound of a number x: it returns an iterator pointing to the element having a value greater than or equal to x in a sorted array.

Upper_bound of a number x: it returns an iterator pointing to the element having a value strictly greater than x in a sorted array.

In this approach, we will use the idea of sorting and searching. First, sort the given array in non-decreasing order. After sorting the array, we will use the binary search algorithm to find the first occurrence of A and B in the sorted array.

We can easily calculate the sum of the elements having a lesser value than A and greater than B. 

We can efficiently calculate the sum using the cumulative sum array. Every index of the cumulative sum array contains the sum of all the elements from the starting index to that index.

Steps of algorithm

• Sort the given array, sort(a, a+n).
• Create a cumulative array of size n (cum[n]). Every index of the cumulative sum array contains the sum of all the elements from the starting index to that particular index.
• We have an A and a B for each query, so if we find the lower bound of A in a given array, we can use the cumulative sum array to get the sum of elements smaller than A. We can also get the sum of the elements greater than B from the cumulative sum array if we find the upper bound of B in the given array.
• For the sum of values greater than B, we subtract the sum of values from 0 to the upper bound of B from the total sum of the array.
• Finally, add both the values and return the sum.

Let’s understand the above approach with an example:

Given array: 

Sorted array:

Cumulative sum array:

Sum = 0

Query1: A = 4, B = 7

Lower_bound of 4 returns index 3, sum = sum + cum[3-1] = 0 + 6 = 6.

Upper_bound of 7 returns index 4 , sum =sum + cum[lastindex] - cum[4-1] = 6 + 29 - 12 = 23.

Query2: A = 2, B = 8

Lower_bound of 2 returns 1, sum = sum + cum[1-1] = 0 + 1 = 1.

Upper_bound of 8 returns index 5 , sum =sum + cum[lastindex] - cum[5-1] = 1 + 29 - 20 = 10.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int sum_A_B(int a[], int n, int A, int B, int cum[])
{
	int sum = 0;

	int indexA = lower_bound(a, a + n, A) - a;

	if (indexA > 0)
		sum = sum + cum[indexA - 1];

	int indexB = upper_bound(a, a + n, B) - a;

	if (indexB > 0)
		sum = sum + (cum[n - 1] - cum[indexB - 1]);

	return sum;
}

int main()
{
	int a[] = { 7, 5, 9, 3, 4 };

	int n = sizeof(a) / sizeof(a[0]);

	sort(a, a + n);

	int cum[n] = { 0 };

	cum[0] = a[0];

	for (int i = 1; i < n; i++)
	{
		cum[i] = cum[i - 1] + a[i];
	}

	int Q;
	cout << " No. of queries: ";
	cin >> Q;

	while (Q--)
	{
		int A, B;

		cout << " Enter A and B: ";

		cin >> A >> B;

		cout << " Sum: " << sum_A_B(a, n, A, B, cum) << endl;
	}

	return 0;

}

You can also try this code with Online C++ Compiler

Run Code

Input:

No. of queries: 1
Enter A and B: 4 6

Output:

Sum: 19

Complexity Analysis

Time complexity: We are sorting the array using the sort function, and for every query, we are using Binary search (lower_bound, upper_bound), so the time complexity is O(max(n*logn, Q*logn)).

Space complexity: O(n) as we are using a cumulative sum array of size n.

Must Read Lower Bound in C++

Frequently Asked Questions

Q1. What is the purpose of binary search?

Answer: In its most basic form, binary search is used to quickly locate a value in a sorted sequence (consider a sequence an ordinary array for now). For the sake of clarity, we'll refer to the desired value as the target value. The target value is always found in a contiguous subsequence of the starting sequence in binary search.

Q2. Where does binary search come into play in real life?

Answer: There are numerous algorithmic tasks that necessitate the use of a binary search to arrive at a model solution. They show up in technical interview questions, code tests, exams, and code challenges.

Q3. In C++, what is the difference between the lower bound and upper bound?

Answer: Lower bound returns an iterator pointing to the first element with a value greater than 'val' in the range [first, last]. The Upper bound returns an iterator pointing to the first element with a value greater than 'val' in the range [first, last].

Key Takeaways

This article discussed the different approaches to finding the sum of elements less than A and greater than B in an array, starting with the brute first approach and then efficient approach with the help of cumulative sum array and binary search with examples and its C++ code.

Check out this problem - Find Duplicate In Array

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!