Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem statement
1.2.
Sample Examples
2.
Brute force approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Efficient approach
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

Problem statement

We are given an array having n elements; we have to answer Q queries. In each query, we are provided with A and B. Our task is to find the sum of all elements having a value lesser than A and greater than B.

Sample Examples

Example 1:

Input: a[] = { 6, 2, 3, 8, 9 ,1 }, Q = 2
Query1: A = 4, B = 7
Query2: A = 2, B = 8

Output:  
23
10

Explanation
Query1: Sum of elements having value lesser than 4 = 1+2+3 = 6, and greater than 7 = 8+9 = 17
Total sum = 6+17 = 23

Query2: Sum of elements having value lesser than 2 = 1, and greater than 8 = 9
Total sum = 1+9 = 10

 

Example 2:

Input: a[]={7, 5, 9, 3, 4}, Q = 1
Query1: A = 4, B = 6

Output: 19

Explanation
Query1: Sum of all the elements having value lesser than 4 = 3, and greater than 6 = 7+9 = 16
Total sum = 19

Recommended topic, kth largest element in an array and  Euclid GCD Algorithm

Brute force approach

The idea is simple, for every query, traverse the whole array. Include the element in the sum if any element’s value in the given array is less than A or greater than B. Else move to the next element. Finally, return the sum.

Steps of algorithm

  • Declare a sum variable and initialise with 0, sum = 0.
  • For every query, run a for loop to traverse the array.
  • Inside the loop, if the current element’s value is lesser than the value of A or greater than the value of B, include the current element in the sum, sum = sum + a[i].
  • Finally, return the value of the sum.

Implementation in C++

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

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

	for (int i = 0; i < n; i++)
	{
		if (a[i] < A || a[i] > B)
			sum += a[i];
	}
	return sum;

}

int main()
{
	int a[] = { 6, 2, 3, 8, 9, 1 };

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

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

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

		cout << " Enter A and B: ";

		cin >> A >> B;

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

	return 0;

}

 

Input:

No. of queries: 2
Enter A and B: 4 7
Enter A and B: 2 8

 

Output:

sum: 23
sum: 10

 

Complexity Analysis

Time complexity: We are traversing the whole array of size n for every query (Q). The time complexity is O(Q*n), where Q and n are the numbers of queries and the number of elements in the given array.

Space complexity: O(1) as we are using constant extra space.

Must Read Lower Bound in C++

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;

}

 

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!

Previous article
Hotel Bookings Possible
Next article
Print Next Greater Number of Q Queries
Live masterclass