Show problems as
Classic problem #1248MediumArrayHash TableMathSliding WindowPrefix Sum

Count Number of Nice Subarrays

Real-world version: Runs With K Odd Readings
Tracked in this browser only
Read Count Number of Nice Subarrays on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A flow meter logs one positive whole number per minute, and the array readings holds the shift in order. A run is any block of consecutive minutes, so it is fixed by the minute it opens on and the minute it closes on, and it always covers at least one minute.

The lab audits a run by counting how many of its readings are odd numbers. A run passes the audit when that count comes to exactly k; a run holding fewer odd readings fails, and so does one holding more.

Tally how many runs of readings pass the audit. Two runs count separately whenever they open or close on different minutes, even if the numbers they hold happen to match.

Examples

Example 1

Input
readings = [7, 12, 5, 4, 4, 9], k = 2
Output
5

Odd readings sit at minutes 0, 2 and 5. The runs holding exactly two of them are [7, 12, 5], [7, 12, 5, 4], [7, 12, 5, 4, 4], [12, 5, 4, 4, 9] and [5, 4, 4, 9].

Example 2

Input
readings = [4, 8, 12], k = 1
Output
0

Every reading on this shift is even, so no run can reach an odd count of one.

Example 3

Input
readings = [3, 5, 7], k = 2
Output
2

All three readings are odd, so a passing run has to cover exactly two neighbouring minutes: [3, 5] or [5, 7].

Constraints

  • 1 <= readings.length <= 50000
  • 1 <= readings[i] <= 10^5
  • 1 <= k <= readings.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def runs_with_k_odd_readings(readings: list[int], k: int) -> int:
Java
public int runsWithKOddReadings(int[] readings, int k)

More on the same topics