Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-
2.
Solution Approach
2.1.
Algorithm -
2.2.
C++ code:
2.3.
Output
2.4.
Algorithm Complexity:
3.
FAQs
4.
Key takeaways-
Last Updated: Mar 27, 2024

Number of Elements less than or equal to a given number in a given subarray

Riya
1 upvote

Introduction-

This blog will discuss the problem of evaluating the queries to find the number of elements less than or equal to a given number in a given subarray.

In this problem, we will be given an array of integers containing ‘N’ elements, and ‘q’ number of queries. Each query is of the form {X, L, R} and for each query, we have to find the number of elements less than or equal to ‘X’ in subarray [L, R] of the given array.

Let's take an example to understand the problem:

Assume the given array and number of queries are:

arr = {2, 4, 3, 6, 9}

q = 3

And the queries are: {{2, 0, 3},  {7, 0, 4}, {3, 0, 2}}

The given queries will be evaluated as follows:

Query 1: {2, 0, 3} = Number of elements less than or equal to 2 in the subarray {2, 4, 3, 6} = 1

Query 1: {7, 0, 4} = Number of elements less than or equal to 7 in the subarray {2, 4, 3, 6, 9} = 4

Query 1: {3, 0, 2} = Number of elements less than or equal to 3 in the subarray {2, 4, 3} = 2

Now that we understand the problem let's discuss the approach to solve it in the next section.

Solution Approach

This section will discuss the approach to find the number of elements less than or equal to a given number in a given subarray. A simple approach is to traverse the given subarray in each query and count the number of elements less than or equal to the given value of ‘X’.

The efficient approach is to use a Binary Indexed tree. We can use a binary indexed tree “bit” array to store the number of elements less than or equal to ‘x’ in arr[0……i] for each value of ‘i’ and then for a query {x, L, R}, calculate the number of elements less than equal to ‘x’ in the range [L, R] as the number of elements less than equal to ‘x’ in the range [0, R] minus the number of elements less than or equal to ‘x’ in the range [0, L-1].

Algorithm -

Step 1. First, the main function. Inside the main function, create an array ‘arr’ to store the given array and a two-dimensional vector to store queries of the form {x, L, R}. Then call the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query.

Step 2. Next, create the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query. It takes following input parameters:

1. arr: Given array of elements
2. queries: A 2-dimensional vector storing the queries of thr form {x, L, R}
3. n: Number of elements in the given array
4. q: Number of queries

Step 3.  Inside the function “evaluateQueries()”, create “bit” array of size ‘n’ and store all its elements as ‘0’ initially. Sort the array ‘arr’ and the ‘queries’ vector accoriding to increasing order of ‘x’. Before sorting the ‘queries’ vector, store the original index of each query.

Step 4. Now, for each query traverse the array till the array elements are less than equal to ‘x’ and update ‘bit’ array. Then store ans for each query as number of elements less than equal to ‘x’ in range [0, R] minus number of elements less than or equal to ‘x’ in range [0, L-1].

Step 5. Finally, write the helper functions “update()” to store the number of elements less than or equal to a given number for each index and “query()” to find the number of elements less than or equal to a given number in a given subarray.

Output

Also read, Euclid GCD Algorithm

Algorithm Complexity:

Time Complexity: O(Q * log(N))

In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, “update()” and “query()” functions having time complexity of log(N), are called for each query. So, the overall time complexity is O(Q * log(N)), where ‘Q’ and 'N' are the number of queries and the number of elements in the array respectively.

Space Complexity: O(N)

In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, we have created a vector 'bit' for Binary indexed tree, so the space complexity is O(N), where 'N' is the number of elements in the given array.

Check out this problem - Count Inversions

FAQs

1. What is a Binary Indexed Tree?
Binary indexed tree also known as fenwick tree is a data structure that stores the elements in an array and helps to calculate the prefix sum efficiently. This data structure is based on the fact that every positive integer can be represented as sum of powers of 2.

2. How the data structure Binary Indexed Tree has helped to optimise the Brute force solution?
In the brute force approach, we have to traverse the given subarray [L, R] given in each query to find the number of elements less than or equal to ‘X’ for each query. But using a binary indexed tree, we can store the number of elements less than or equal to ‘x’ in arr[0……i] for each value of ‘i’ and then for a query {x, L, R}, calculate the number of elements less than equal to ‘x’ in the range [L, R] as the number of elements less than equal to ‘x’ in the range [0, R] minus the number of elements less than or equal to ‘x’ in the range [0, L-1]. The time complexity for both updating the “bit” array and calculating the number of elements less than or equal to ‘x’ in the range [L, R] is logarithmic.

Key takeaways-

This article discussed the problem of evaluating the queries to find the number of elements less than or equal to a given number in a given subarray using binary indexed tree, its C++ implementation, and its time and space complexity. If you want to solve more problems on data structure and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavours and Keep Coding.

Live masterclass