You are given an array of integers sorted in non-decreasing order and an inclusive query range [lo, hi] with lo <= hi. Count how many array values v satisfy lo <= v <= hi. Duplicate values each count separately.
The intended solution locates the lower bound of lo and the upper bound of hi with two binary searches and returns the difference of their positions, giving an O(log n) query.
Line 1: an integer n, the length of the array.
Line 2: n space-separated integers in non-decreasing order (this line is empty when n = 0).
Line 3: two space-separated integers lo and hi with lo <= hi.
A single integer: the count of array values inside the inclusive range [lo, hi].
Example 1
Input
8 1 2 2 2 5 7 7 10 2 7
Expected
6
Explanation
The values inside [2, 7] are 2, 2, 2, 5, 7, 7 — six of them.
Example 2
Input
6 -5 -2 0 3 8 8 1 4
Expected
1
Explanation
Only the value 3 lies in [1, 4], so the count is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →