275. How Many Fall in the Range
Core1000 ms256 MBSolved by 0%
Given n integers and two bounds lo and hi, print how many values
satisfy lo <= value <= hi. Both bounds are inclusive.
Counting by scanning is O(n) and perfectly fine for one question. Sorting
first costs O(n log n) once and then answers this in O(log n), which is
the arrangement you want when many ranges are asked about the same data.
Both endpoints are lower bounds, which is why that one search keeps earning its place.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ lo ≤ hi ≤ 1000000000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains three integers n, lo and hi.
The second line contains n integers.
Output
Print one integer, the count of values within the inclusive range.
Input5 2 4
1 2 3 4 5
Output3
Notehas a range covering three of five values
Input3 5 10
1 2 3
Output0
Notehas a range entirely above the data
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.