How many readings fall in the band
A sorted column of measurements is checked against a tolerance band, and the report wants the count inside it — over millions of rows, so scanning is out.
- The readings arrive sorted ascending.
- Both ends of the band are inclusive.
- A band that runs backwards contains nothing.
- Return how many readings fall inside.
countInBand(readings: list<int>, low: int, high: int) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int countInBand(std::vector<int> readings, int low, int high) {
}Worked examples
| Call | Result |
|---|---|
countInBand(std::vector<int>{1, 3, 5, 7, 9}, 3, 7) | 3 |
countInBand(std::vector<int>{1, 3, 5, 7, 9}, 4, 4) | 0 |
countInBand(std::vector<int>{2, 2, 2, 2}, 2, 2) | 4 |
countInBand(std::vector<int>{1, 2, 3}, 3, 1) | 0 |
Hint
Two binary searches: the first position not below the low end, and the first position above the high end. The gap between them is the answer.
Reference solution in C++
int countInBand(std::vector<int> readings, int low, int high) {
if (low > high) return 0;
auto lowerBound = [&](int target) {
int lo = 0, hi = static_cast<int>(readings.size());
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
};
return lowerBound(high + 1) - lowerBound(low);
}