A survey published only a grouped table of commuting times. The bands are consecutive and all width minutes wide: band 0 covers start to start + width, band 1 the next width minutes, and so on, and counts[i] is the number of people in band i. The individual times are lost.
To estimate the median anyway, assume that the people in each band are spread evenly across it: with 4 people in the band from 20 to 30, a quarter of the band's people lie in every 2.5 minutes. Under that assumption, return the smallest time t such that exactly half of all people have a time up to t.
Write estimated_median(start, width, counts) that returns this estimate as a float, or None if the table holds nobody.
Examples
Input: start = 0, width = 10, counts = [4, 10, 16, 6, 4]
Output: 23.75
Explanation: 40 people, so the median sits where 20 people have been counted.
The first two bands hold 14, so 6 more of the 16 in the band 20-30 are needed:
6 / 16 of the way through it, at 20 + 3.75 = 23.75.
Input: start = 5, width = 5, counts = [3, 0, 3]
Output: 10.0
Explanation: half of the 6 people (3) are reached at the end of the first band, 10.
Constraints
1 <= len(counts) <= 10**5, every count a whole number with0 <= count <= 10**6startandwidthare whole numbers,0 <= start <= 1000,1 <= width <= 100- answers are compared with a small tolerance
Goals
- Estimate a median when only a grouped table is known
- Find the band that holds the middle with cumulative counts
- Place the median inside that band by assuming its values are spread evenly