Given an array of N integers. There will be Q queries, each include two integer of form q and x, 0 <= q <= 1. Queries are of two types:
- In first query (q = 0), the task is to find count of integers which are not less than x (OR greater than or equal to x).
- In second query (q = 1), the task is to find count of integers greater than x.
Examples:
Input : arr[] = { 1, 2, 3, 4 } and Q = 3
Query 1: 0 5
Query 2: 1 3
Query 3: 0 3
Output :0
1
2
Explanation:
x = 5, q = 0 : There are no elements greater than or equal to it.
x = 3, q = 1 : There is one element greater than 3 which is 4.
x = 3, q = 0 : There are two elements greater than or equal to 3.
Method 1: A Naive approach can be for each query, traverse the whole array and count integers less or greater than x, depending on q. Time Complexity for this approach will be O(Q*N).
Method 2: An efficient approach can be sort the array and use binary search for each query. This will take O(NlogN + QlogN).
Below is the implementation of this approach :
C++
// C++ to find number of integer less or greater given // integer queries #include<bits/stdc++.h> using namespace std; // Return the index of integer which are not less than x // (or greater than or equal to x) int lower_bound(int arr[], int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] >= x) end = mid; else start = mid + 1; } return start; } // Return the index of integer which are greater than x. int upper_bound(int arr[], int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] <= x) start = mid + 1; else end = mid; } return start; } void query(int arr[], int n, int type, int x) { // Counting number of integer which are greater than x. if (type) cout << n - upper_bound(arr, 0, n, x) << endl; // Counting number of integer which are not less than x // (Or greater than or equal to x) else cout << n - lower_bound(arr, 0, n, x) << endl; } // Driven Program int main() { int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); sort(arr, arr + n); query(arr, n, 0, 5); query(arr, n, 1, 3); query(arr, n, 0, 3); return 0; } |
Java
// Java to find number of integer // less or greater given // integer queries import java.util.Arrays; class GFG { // Return the index of integer // which are not less than x // (or greater than or equal // to x) static int lower_bound(int arr[], int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] >= x) end = mid; else start = mid + 1; } return start; } // Return the index of integer // which are greater than x. static int upper_bound(int arr[], int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] <= x) start = mid + 1; else end = mid; } return start; } static void query(int arr[], int n, int type, int x) { // Counting number of integer // which are greater than x. if (type==1) System.out.println(n - upper_bound(arr, 0, n, x)); // Counting number of integer which // are not less than x (Or greater // than or equal to x) else System.out.println(n - lower_bound(arr, 0, n, x)); } // Driver code public static void main (String[] args) { int arr[] = { 1, 2, 3, 4 }; int n = arr.length; Arrays.sort(arr); query(arr, n, 0, 5); query(arr, n, 1, 3); query(arr, n, 0, 3); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find number of integer # less or greater given integer queries # Return the index of integer # which are not less than x # (or greater than or equal to x) def lower_bound(arr, start, end, x): while (start < end): mid = (start + end) >> 1 if (arr[mid] >= x): end = mid else: start = mid + 1 return start # Return the index of integer # which are greater than x. def upper_bound(arr, start, end, x): while (start < end): mid = (start + end) >> 1 if (arr[mid] <= x): start = mid + 1 else: end = mid return start def query(arr, n, type, x): # Counting number of integer # which are greater than x. if (type == 1): print(n - upper_bound(arr, 0, n, x)) # Counting number of integer # which are not less than x # (Or greater than or equal to x) else: print(n - lower_bound(arr, 0, n, x)) # Driver code arr = [ 1, 2, 3, 4 ] n =len(arr) arr.sort() query(arr, n, 0, 5) query(arr, n, 1, 3) query(arr, n, 0, 3) # This code is contributed by Anant Agarwal. |
C#
// C# to find number of integer less // or greater given integer queries using System; class GFG { // Return the index of integer which are // not less than x (or greater than or // equal to x) static int lower_bound(int []arr, int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] >= x) end = mid; else start = mid + 1; } return start; } // Return the index of integer // which are greater than x. static int upper_bound(int []arr, int start, int end, int x) { while (start < end) { int mid = (start + end)>>1; if (arr[mid] <= x) start = mid + 1; else end = mid; } return start; } static void query(int []arr, int n, int type, int x) { // Counting number of integer // which are greater than x. if (type==1) Console.WriteLine(n - upper_bound(arr, 0, n, x)); // Counting number of integer which // are not less than x (Or greater // than or equal to x) else Console.WriteLine(n - lower_bound(arr, 0, n, x)); } // Driver code public static void Main () { int []arr = {1, 2, 3, 4}; int n = arr.Length; Array.Sort(arr); query(arr, n, 0, 5); query(arr, n, 1, 3); query(arr, n, 0, 3); } } // This code is contributed by vt_m. |
PHP
<?php // PHP to find number of integer // less or greater given // integer queries // Return the index of integer // which are not less than x // (or greater than or equal to x) function lower_bound($arr, $start, $end, $x) { while ($start < $end) { $mid = ($start + $end) >> 1; if ($arr[$mid] >= $x) $end = $mid; else $start = $mid + 1; } return $start; } // Return the index of integer // which are greater than x. function upper_bound($arr, $start, $end, $x) { while ($start < $end) { $mid = ($start + $end) >> 1; if ($arr[$mid] <= $x) $start = $mid + 1; else $end = $mid; } return $start; } function query($arr, $n, $type, $x) { // Counting number of integer // which are greater than x. if ($type) echo $n - upper_bound($arr, 0, $n, $x) ,"\n"; // Counting number of integer // which are not less than x // (Or greater than or equal to x) else echo $n - lower_bound($arr, 0, $n, $x) ,"\n"; } // Driver Code $arr = array(1, 2, 3, 4); $n = count($arr); sort($arr); query($arr, $n, 0, 5); query($arr, $n, 1, 3); query($arr, $n, 0, 3); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find number of integer // less or greater given // integer queries // Return the index of integer // which are not less than x // (or greater than or equal // to x) function lower_bound(arr, start, end, x) { while (start < end) { let mid = (start + end)>>1; if (arr[mid] >= x) end = mid; else start = mid + 1; } return start; } // Return the index of integer // which are greater than x. function upper_bound(arr, start, end, x) { while (start < end) { let mid = (start + end)>>1; if (arr[mid] <= x) start = mid + 1; else end = mid; } return start; } function query(arr, n, type, x) { // Counting number of integer // which are greater than x. if (type==1) document.write(n - upper_bound(arr, 0, n, x) + "<br/>"); // Counting number of integer which // are not less than x (Or greater // than or equal to x) else document.write(n - lower_bound(arr, 0, n, x) + "<br/>"); } // Driver code let arr = [ 1, 2, 3, 4 ]; let n = arr.length; arr.sort(); query(arr, n, 0, 5); query(arr, n, 1, 3); query(arr, n, 0, 3); </script> |
Output:
0 1 2
Time Complexity : O( (N + Q) * logN).
Auxiliary Space : O(1)
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
