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
Java 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(List<Integer> readings, int low, int high) {
}Worked examples
| Call | Result |
|---|---|
countInBand(Main.<Integer>ls(1, 3, 5, 7, 9), 3, 7) | 3 |
countInBand(Main.<Integer>ls(1, 3, 5, 7, 9), 4, 4) | 0 |
countInBand(Main.<Integer>ls(2, 2, 2, 2), 2, 2) | 4 |
countInBand(Main.<Integer>ls(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 Java
int countInBand(List<Integer> readings, int low, int high) {
if (low > high) return 0;
int[] bounds = new int[2];
int[] targets = { low, high + 1 };
for (int t = 0; t < 2; t++) {
int lo = 0, hi = readings.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings.get(mid) < targets[t]) lo = mid + 1;
else hi = mid;
}
bounds[t] = lo;
}
return bounds[1] - bounds[0];
}