Stretches With k Odd Numbers

Medium

You get an integer array values and a number odd_count. Count the contiguous stretches (subarrays) of the array that contain exactly odd_count odd numbers. Stretches with different boundaries are counted separately, even if they hold the same numbers.

Example 1

values=[3, 8, 5, 6, 7], odd_count=2 → 4

Exactly two odd numbers are found in [3, 8, 5], [3, 8, 5, 6], [5, 6, 7] and [8, 5, 6, 7], so the answer is 4.

Example 2

values=[10, 12], odd_count=1 → 0

The array has no odd numbers at all.

Example 3

values=[1, 1, 1], odd_count=1 → 3

Constraints

1 ≤ len(values) ≤ 50,000
1 ≤ values[i] ≤ 10⁵
1 ≤ odd_count ≤ len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Math Prefix Sum Sliding Window

Similar problems

A Stretch Divisible by k Medium Windows With an Exact Alarm Count Medium Split Into Equal-XOR Halves Medium Trim the Ends to a Target Medium A Stretch of a Looping Playlist Medium

Input

values=[3, 8, 5, 6, 7], odd_count=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.