Exactly zero degrees
You are given a series of daily mean temperatures over n days in tenths of a degree, and a number k. How many periods of consecutive days have a mean temperature of exactly k/10 degrees? A period is anything from one day to the whole series; different periods are counted separately even if they overlap.
Tests two to four are Almaty’s daily mean temperature for 1941–2025 (the ERA5 reanalysis via Open-Meteo): 31,046 days, with exactly zero, ten and 8.7 degrees.
Input
The first line holds n and k (1 ≤ n ≤ 2·10⁵, |k| ≤ 1000), the second n integers of absolute value at most 1000.
Output
One number: the count of periods.
Examples
Example 1
7 0 -20 15 5 0 -10 10 0
10
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A mean of exactly k is the same as the deviations from k summing to zero. Subtract k from every day. What can then be said about the prefix sums at the ends of such a period?
2The idea
Let P[i] be the sum of the first i deviations t − k. The sum of the deviations over days i + 1 to j is P[j] − P[i], and it is zero exactly when P[i] = P[j]. So what is needed is to count pairs of equal prefix sums.
3Walkthrough
Walk along the series keeping a hash table of how many times each prefix sum has occurred so far. Start with the sum 0 seen once: the empty beginning of the series. At each step the new sum forms a pair with every equal sum from the past: add its counter to the answer and increase it.
Checking all periods via prefix sums is also a correct solution, but there are n(n + 1)/2 periods: 4.8·10⁸ for the real series, 2·10¹⁰ for 2·10⁵ days.
The answer can be huge: if every day is exactly k (the sixth test), every period fits, and there are about 2·10¹⁰ of them.
3+Solution
4Complexity
O(n) on average: one hash-table operation per day. Memory O(n) for the counters.
5Common mistakes
- Forgetting the empty beginning. Without the initial sum 0, all the periods that start on the first day are lost.
- Working with means rather than sums. Division gives fractions, and the comparison “the mean equals k/10” in floating point can go wrong. A sum of deviations is an integer.
- A 32-bit answer. In the sixth test the answer is more than two billion.
Algorithms behind it
O(n) to build, O(1) per query
2 problems
DS
Data structure
Hash table
Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell.
O(1) on average
2 problems