Free Hashing lessonsHashing · Stage 2 · Counting with maps · Step 4

Count what came before

Count stretches with exactly k odd numbers, using running counts in a map. About 10 minutes.

Turn the question into 0s and 1s

How many stretches contain exactly k odd numbers? It sounds new, but squint at it: mark each odd number 1 and each even number 0. A stretch has k odd numbers exactly when its 1s add up to k.

That's the "stretches that add up to k" problem from Arrays, just on 0s and 1s. Re-using a problem you've solved is one of the best tricks there is.

Odd is 1, even is 0: now it's a sum problem you know.

nums = [1, 1, 2, 1, 1], k = 3

odds: 1
seen: {0: 1, 1: 1}
total: 0

Running count of odd numbers: 1. Look up 1 - 3 = -2: never seen.

Move 1 of 5

Look up the partner count

Keep a running count of odd numbers as you walk. A stretch ending here has k odds when it starts just after a point where the running count was k lower. A map says how many such points there were, so add that.

Start the map with the count 0 seen once, for the start of the list. And in some languages the remainder of a negative odd number is −1, so test "remainder isn't 0" rather than "remainder is 1".

Negative numbers: test for a non-zero remainder.

In code

seen = {0: 1}
odds = total = 0
for x in nums:
    if x % 2 != 0:
        odds += 1
    total += seen.get(odds - k, 0)
    seen[odds] = seen.get(odds, 0) + 1
return total

Quick check

You've seen 5 odd numbers so far and k is 2. Which earlier running count do you look up?

Show the answer

3. From a point with 3 odds to here with 5, the stretch holds 2.

Your problem

Stretches with k odd numbers

Count the non-empty runs of consecutive numbers that contain exactly k odd numbers.

Example

nums = [1, 1, 2, 1, 1], k = 3 → 2

0 ≤ n ≤ 1,000,000 · 1 ≤ k ≤ n · values may be negative · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.